(27) 32. 最长有效括号

题目链接： https://leetcode-cn.com/problems/longest-valid-parentheses/ 难度：困难 32. 最长有效括号 给定一个只包含 '(' 和 ')' 的字符串，找出最长的 包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

这个题不是特别难 还是有些思路的 我对于这种题 第一思路就是栈 匹配问题还是挺合适的 不过有几个需要注意的地方 犯错了。。

class Solution { public: int longestValidParentheses(string s) { int n=s.size(); // int 要计算长度 存入为下标 stack<int> sta; // push -1 方便 // 不用考虑 栈初始为空需要pop的情况 // 不用进行加一操作 sta.push(-1); int maxlength=0; int i=0; while(i<n){ if (s[i]=='('){ // ( 直接push sta.push(i); }else{ // 直接pop （开始时 push -1 必不为空） sta.pop(); // 若为空 出错 将当前出错的i push // 在进行计算长度时i-出错时的位置（不用加一） if (sta.empty()){ sta.push(i); }else{ // 不为空说明正确 计算并更新 maxlength=max(maxlength,i-sta.top()); } } i++; } return maxlength; } };

还有一种方法是动态规划 没有想到 转换放方程也不太好想 看的解析。。。 dp[i] 代表以下标 i 字符结尾的最长有效括号的长度 有效字符串 比以 ‘)’ 结尾 只考虑 “()” “))” 两种情况 对于 “()” dp[i]=dp[i-2]+2; 对于 “))” 若s[i−dp[i−1]−1]=‘(’ 则dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

class Solution { public: int longestValidParentheses(string s) { int maxans = 0, n = s.length(); vector<int> dp(n, 0); for (int i = 1; i < n; i++) { if (s[i]==')'){ if (s[i-1]=='('){ dp[i]=i>2?dp[i-2]+2:2; }else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '('){ dp[i]=dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2; } } maxans = max(maxans, dp[i]); } return maxans; } };

看了下解析 还有一种思路 自己写了一下 我只想说妙啊 对于字符串s left和right分别记录’(’ ‘)’ 的数量 那么我们可以分析

从左向右遍历 若 left==right 那么更新最大长度 若left<right 那么left=right=0 考虑 “(()” 这种情况下 使用上面一种方法是不可的 所以 同样的道理从右向左遍历 若 left==right 那么更新最大长度 若left>right 那么left=right=0 class Solution { public: int longestValidParentheses(string s) { int left = 0, right = 0, maxlength = 0; for(int i=0;i<s.size();i++){ if (s[i]=='(') left++; else right++; if (left==right){ maxlength=max(maxlength,2*right); }else if(right>left){ right=0; left=0; } } left = 0, right = 0; for(int i=s.size()-1;i>=0;i--){ if (s[i]==')') right++; else left++; if (left==right){ maxlength=max(maxlength,2*right); }else if(left>right){ right=0; left=0; } } return maxlength; } };