【算法day25】 最长有效括号——给你一个只包含 ‘(‘ 和 ‘)‘ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

32. 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

https://leetcode.cn/problems/longest-valid-parentheses/

2.方法二：栈

class Solution {
public:int longestValidParentheses(string s) {int max_len = 0, cur_len = 0;stack<pair<char,int>> sub_s;sub_s.push({' ',-1 });for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {sub_s.push({'(',i});}else {// 如果是）的话if (sub_s.top().first == -1) {// 不可能出现匹配了，记录失配点sub_s.push({ ')',i });}else {// 栈里有个(if (sub_s.top().first == '(') {sub_s.pop();cur_len = i - sub_s.top().second;if (max_len < cur_len) {max_len = cur_len;}}else {// 否则失配sub_s.push({ ')',i });}}}}return max_len;}
};

1.方法一：动态规划

class Solution {
public:int longestValidParentheses(string s) {if (s.size() <= 1) {return 0;}vector<int> dp(s.size());dp[0] = 0;int max_len = 0;for (int i = 1; i < s.size(); i++) {if (s[i] == ')' && s[i - 1] == '(') {// 是()()()这样连着的，就可以逐个累积if (i > 2) {dp[i] = 2 + dp[i - 2];} else {dp[i] = 2;}} else if (s[i] == ')' && s[i - 1] == ')') {// ……)) 这样的样子，可能是// 情况1：()) 不匹配// 情况2：(()) 匹配了并且前面没有可以匹配的了// 情况3：()()()(())匹配而且前面还有可以匹配的if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {if (i - dp[i - 1] - 2 >= 0) {dp[i] = dp[i - dp[i - 1] - 2] + 2 + dp[i - 1];} else {dp[i] = dp[i - 1] + 2;}} else {dp[i] = 0;}} else {dp[i] = 0;}if (max_len < dp[i]) {max_len = dp[i];}}return max_len;}
};

方法三：贪心算法

我觉得这个方法有点类似这个题的算法：

【算法day19】括号生成——数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合

也就是说，通过判断左右括号的数量来判断是否匹配

但是这个算法没有考虑()(((()的情况，这个显然左括号很多，但是右括号严重缺少。
所以我们从右往左再类似地看一次，这次判断 ，左括号数大于右括号数，就失配，令当前匹配数量为0.

class Solution {
public:int longestValidParentheses(string s) {int cur_len = 0, max_len = 0;int left_num = 0, right_num = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {++left_num;} else if (s[i] == ')') {++right_num;}if (right_num > left_num) {right_num = 0;left_num = 0;} else if(right_num==left_num){cur_len = 2 * min(left_num, right_num);if (cur_len > max_len) {max_len = cur_len;}}}left_num = 0, right_num = 0;for (int i = s.size() - 1; i < s.size(); i--) {if (s[i] == '(') {++left_num;} else if (s[i] == ')') {++right_num;}if (right_num < left_num) {right_num = 0;left_num = 0;} else if (right_num == left_num) {cur_len = 2 * min(left_num, right_num);if (cur_len > max_len) {max_len = cur_len;}}}return max_len;}
};