60 最长有效括号

题目描述

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

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"示例 3：
输入：s = ""
输出：0

题解1 DP+stack

class Solution {
public:int longestValidParentheses(string s) {int st = s.size();if(0 == st) return 0;stack<int> stk;vector<int> dp(st+1, 0);for(int i = 0; i < st; i++){if(s[i] == '('){stk.push(i);// 如果是左括号说明i位置不会有效，对应在dp里i+1位置置零即可dp[i+1] = 0;}else{if(! stk.empty()){// 如果没有stack，递推公式稍微复杂一点// key：别忘了+dp[stk.top()]// 以防迷惑：stk.top()是最近的左括号下标值，dp[stk.top()+1]=0dp[i+1] = i + 1 - stk.top() + dp[stk.top()];stk.pop(); }else dp[i+1] = 0;}}int ret = INT_MIN;for(auto& i : dp){ret = max(ret, i);}return ret;}
};

题解2 stack

class Solution {
public:int longestValidParentheses(string s) {int st = s.size();if(0 == st) return 0;stack<int> stk;// 处理第一个字符是左括号的情况stk.push(-1);int ret = 0;for(int i = 0; i < st; i++){if(s[i] == '('){stk.push(i);}else{// 遇到右括号，先弹栈（遇到右括号，前面的连续有效括号就作废了）stk.pop();if(! stk.empty()){ret = max(ret, i-stk.top());}else {stk.push(i);}}}return ret;}
};

题解3 DP

class Solution {
public:int longestValidParentheses(string s) {int st = s.size();if(0 == st) return 0;vector<int> dp(st, 0);int maxS = 0; for(int i = 1; i < st; i++){if(s[i] == ')'){// "()()"if(s[i-1] == '('){dp[i] = 2;// 前面还有项（如果有stack就会马上定位到上一个有效序列的开始）if(i >= 2)dp[i] = dp[i-2] + dp[i];}// "(())"else if(dp[i-1]){if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '('){dp[i] = dp[i-1] + 2;// 前面还有项if(i - dp[i-1] - 2 >= 0)dp[i] = dp[i] + dp[i - dp[i - 1] - 2];}    }                    }maxS = max(maxS, dp[i]);}return maxS;}
};

题解4 左右指针

class Solution {
public:int longestValidParentheses(string s) {int left = 0, right = 0, maxlength = 0;// 左扫for (int i = 0; i < s.length(); i++) {if (s[i] == '(') {left++;} else {right++;}if (left == right) {maxlength = max(maxlength, 2 * right);} else if (right > left) {left = right = 0;}}left = right = 0;// 右扫：解决左扫扫不出来的"(((()"for (int i = (int)s.length() - 1; i >= 0; i--) {if (s[i] == '(') {left++;} else {right++;}if (left == right) {maxlength = max(maxlength, 2 * left);} else if (left > right) {left = right = 0;}}return maxlength;}
};