原题

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

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

示例 2:

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

解法

思想

见代码部分

代码

动态规划解法：

dp[i]代表截至到某个元素的包含有效括号的子串的最长长度（必须包含该字符）。

那么若s.charAt(i) == '('，则dp[i]必为0。若s.charAt(i) == ')'，分情况：
+ s.charAt(i-1) == '('，则字符串是...()的形式，此时的dp[i] == dp[i-2]+2。
+ s.charAt(i-1) == ')'，则字符串是...))的形式，此时要看与s.charAt(i-1)相匹配的左括号的前一个字符是否为(，若是，则dp[i] == dp[i-1]+2+dp[prev-1]，若不是，则dp[i] == 0。

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        int[] dp = new int[s.length()];
        for(int i = 1;i<dp.length;i++){
            if(s.charAt(i) != '('){ 
                if(s.charAt(i-1) == '('){
                    int prev = i>=2?dp[i-2]:0;
                    dp[i] = prev + 2;
                    if(dp[i]>max) max = dp[i];
                }else{
                    int prev = i-dp[i-1]-1;
                    if(prev>=0 && s.charAt(prev) == '('){
                        dp[i] = dp[i-1]+2 + (prev==0?0:dp[prev-1]);
                        if(dp[i]>max) max = dp[i];
                    }
                }
            }
        }
        return max;
    }
}

栈的解法需要一些精妙的设计，要保证栈底必须有一个元素（始终留下一个最左边没参与匹配的下标在栈内）：

public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode32-%e6%9c%80%e9%95%bf%e6%9c%89%e6%95%88%e6%8b%ac%e5%8f%b7/