代码1

Runtime: 9 ms, faster than 8.31% of Java online submissions for Longest Valid Parentheses.

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    if (s.charAt(stack.peek()) == '(') {
                        stack.pop();
                    } else {
                        stack.push(i);
                    }
                } else {
                    stack.push(i);
                }
            }
        }
        int a = s.length();
        int b = 0;
        int length = 0;
        while (!stack.isEmpty()) {
            b = stack.pop();
            length = Math.max(length, a - b - 1);
            a = b;
        }
        length = Math.max(length, a);
        return length;
    }
}

代码1

dp
Runtime: 2 ms, faster than 71.94% of Java online submissions for Longest Valid Parentheses.

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == ')' && i - 1 >= 0) {
                //read dp[i-1] to get index of "(" related to ")" in this position
                int checkLeftIndex = i - 1 - dp[i - 1];
                if (checkLeftIndex >= 0 && s.charAt(checkLeftIndex) == '(') {
                    //case "(( ))" , dp = {0,0,2,2+2}
                    dp[i] = dp[i - 1] + 2;
                    //Case"() (())", dp = {0,2,0,0,2,2+2+2}
                     if(checkLeftIndex - 1 >= 0){
                        dp[i] += dp[checkLeftIndex - 1];
                    }
                    ans = Math.max(ans,dp[i]);
                }
            }
        }
        return ans;
    }
}