32 最长有效括号 DP 栈模拟

注意题目的理解，这个有效子串里每个左括号都能找到对应的右括号就是有效的，不是说非要（）（）两两挨着

没想出来这种状态定义方法官方答案

注意dp是表示已下标i字符为结尾的有效字符串的长度，即下标i字符必须在有效字符串的结尾，而不是以i结尾的字符串的最大有效字符串长度。

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         int maxans = 0, n = s.length();
 5         vector<int> dp(n, 0);
 6         for (int i = 1; i < n; i++) {
 7             if (s[i] == ')') {
 8                 if (s[i - 1] == '(') {
 9                     dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
10                 } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
11                     dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
12                 }
13                 maxans = max(maxans, dp[i]);
14             }
15         }
16         return maxans;
17     }
18 };
19 
20 作者：LeetCode-Solution
21 链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
22 来源：力扣（LeetCode）
23 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

栈模拟方法

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         int maxans = 0;
 5         stack<int> stk;
 6         stk.push(-1);
 7         for (int i = 0; i < s.length(); i++) {
 8             if (s[i] == '(') {
 9                 stk.push(i);
10             } else {
11                 stk.pop();
12                 if (stk.empty()) {
13                     stk.push(i);
14                 } else {
15                     maxans = max(maxans, i - stk.top());
16                 }
17             }
18         }
19         return maxans;
20     }
21 };
22 
23 作者：LeetCode-Solution
24 链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
25 来源：力扣（LeetCode）
26 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

每天进步一点点~