括号"/>
60 最长有效括号
最长有效括号
- 题目描述
- 题解1 DP+stack
- 题解2 stack
- 题解3 DP
- 题解4 左右指针
题目描述
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 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;}
};
更多推荐
60 最长有效括号
发布评论