输入 : "(()" 输出 : 2 解释 : 最长有效括号子串为 "()" 

 输入 : ")()())" 输出 : 4 解释 : 最长有效括号子串为 "()()" 

 * 栈顶保存的是 `')'`，如果是这种情况，表示前面没有可配对的 `'('`，我们此时还是需要把当前 _index_ 入栈，原因是 我们确定距离需要知道边界，如果不理解，还是有两个例子供你参考： ``` "))(())" "())()()" 

 ### **代码实现** 

 public int longestValidParentheses(String s) { if (s == null || s.length() == 0) { return 0; } int n = s.length(); char[] sArr = s.toCharArray(); Stack stack = new Stack<>(); int result = 0; // -1 入栈用于处理边界条件 stack.push(-1); for (int i = 0; i < n; ++i) { // stack.size() > 1 表示栈不为空，而且我们必须保证栈顶元素是 '(' if (sArr[i] == ')' && stack.size() > 1 && sArr[stack.peek()] == '(') { // 配对的 '(' 出栈 stack.pop(); // 记录长度 result = Math.max(result, i - stack.peek()); } else { // 其他情况，直接将当前位置入栈 stack.push(i); } } return result; } 

 ### **动画理解** ** ** ### ### **解法二：动态规划** 如果用 **栈** 来解决的话，这道题思路差不多就是这样。考虑到前不久一直聊 **动态规划**，于是试了一下用把它归纳到 **序列型动态规划** 来求解。 我们可以定义 **dp[i] 表示的是 str[0…i] 的答案**，思路其实和前面很类似： 1、从左到右遍历输入的字符串 2、如果遇到的是 '('，意味着这并不能和前面遍历过的部分组成合法答案，因为 dp 状态数组中记录的是答案，这个时候说明 dp[i] = 0，也就是不用做任何记录 3、如果遇到的是 ')'，这时我们还是需要往前看： * 如果 str[i - 1] 是 '('，那么 dp[i] = dp[i - 2] + 2 * 如果 str[i - 1] 是 ')'，这表示 str[i - 1] 已经配对了，因此我们还要继续往前看，从当前位置往左，看第一个没有被配对的 '('，怎么找这个位置呢，这里我们就可以利用 dp[i - 1] 这个信息，dp[i - 1] 表示的是之前匹配的长度，那么 ： * **i - dp[i - 1] - 1** 表示的就是从当前位置往左，第一个没有被配对的位置 * 如果位置 i 和 位置 i - dp[i - 1] - 1 配对后，我们可以看看当前的序列是否可以和之前匹配的序列链接起来，也就是加上 dp[i - dp[i - 1] - 2] ### ### **代码实现** 

 public int longestValidParentheses(String s) { if (s == null || s.length() == 0) { return 0; } int n = s.length(); char[] sArr = s.toCharArray(); int[] dp = new int[n]; int result = 0; for (int i = 1; i < n; ++i) { if (sArr[i] == ')') { // 如果前一个位置是 '('，直接配对 if (sArr[i - 1] == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } // 前一个位置是 ')' // 我们从当前位置往左看，如果第一个没有被匹配的位置是 '(' // 表明当前位置是可以被匹配的 else if (i - dp[i - 1] - 1 >= 0 && sArr[i - dp[i - 1] - 1] == '(') { // 这里其实是 dp[i] = i - (i - dp[i - 1] - 1) + 1 = dp[i - 1] + 2 // 但是我们还需要考虑之前的答案，也就是 dp[i - dp[i - 1] - 2] // 首先判断 i - dp[i - 1] - 2 是否越界 // 如果没有越界就将其加上 dp[i] = dp[i - 1] + 2; if (i - dp[i - 1] >= 2) { dp[i] += dp[i - dp[i - 1] - 2]; } } result = Math.max(result, dp[i]); } } return result; } 

 两种方法时空复杂度都是 O(n)，解法也有相似之处，只是说切题点不一样。 ![一道 LeetCode 的多种解法，打消了我的自以为是！](https://img.chainnews.com/material/images/01c11d97ab471e088eb9eb026afad33a.jpg) 正当我美滋滋时，突然看到另外一种解法，让我感觉自己的智商受到了碾压：**不需要额外的空间**，空间复杂度是 O(1) ！ ### **解法三：借助变量** 使用了两个变量 Left 和 Right，分别用来记录到当前位置时左括号和右括号的出现次数。 当遇到左括号时，Left 自增 1，右括号时 Right 自增 1。 对于最长有效的括号的子串，一定是左括号等于右括号的情况，此时就可以更新结果 res 了，一旦右括号数量超过左括号数量了，说明当前位置不能组成合法括号子串，Left 和 Right 重置为 0。 但是对于这种情况 "(()" 时，在遍历结束时左右子括号数都不相等，此时没法更新结果 res，但其实正确答案是 2，怎么处理这种情况呢？ 答案是再 **反向遍历一遍** ，采取类似的机制，稍有不同的是此时若 Left 大于 Right 了，则重置 0，这样就可以涵盖所有情况。 ### **代码实现** 

 // 代码来源：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/ public class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, maxlength = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * right); } else if (right >= left) { left = right = 0; } } left = right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * left); } else if (left >= right) { left = right = 0; } } return maxlength; } }