32. 最长有效括号 - 困难

https://leetcode-cn.com/problems/longest-valid-parentheses/submissions/

我的解 - 滑动窗口 - 太慢

class Solution {
    public int longestValidParentheses(String s) {
        int leftNum = 0;
        int rightNum = 0;
        int left = 0;
        int right = 0;
        int max = 0;
        Map<Integer,Integer> map = new HashMap<>();
        char[] cs = s.toCharArray();
        while(left < s.length() - 1){
            right = left;
            leftNum = 0;
            rightNum = 0;
            while(right < s.length()){
                if(cs[right] == ')'){
                    if(leftNum <= rightNum){
                        right++;
                        while(right < s.length() && cs[right] == ')') right++;
                        left = right - 1;
                        break;
                    }
                    rightNum++;
                }else{
                    leftNum++;
                }
                right++;
                if(leftNum == rightNum){
                    max = Math.max(max, right-left);
                }
            }
            left++;
        }
        return max;
    }
}

动态规划

public class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int dp[] = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 考虑一下这种情况 ()(()())
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

栈

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;
    }
}

递归 + 中心扩展

class Solution {
    // (right, left)
private Map<Integer, Integer> map = new HashMap<>();
// key: 右括号的索引, value: 对应左括号的索引

    public int longestValidParentheses(String s) {
        char[] arr = s.toCharArray();
        int max = 0;
        // 遍历中心
        for (int c = 0; c < arr.length - 1; c++) {
            if (arr[c] == '(' && arr[c + 1] == ')') {
                int r = expand(arr, c, c + 1);
                max = Math.max(max, r - map.get(r) + 1);
                c = r;
            }
        }
        return max;
    }

    // 中心扩展
    private int expand(char[] arr, int l, int r) {
        while (l >= 0 && r < arr.length && arr[l] == '(' && arr[r] == ')') {
            l--; r++;
        }
       //map.put(r - 1, l + 1);
        if (map.containsKey(l)) return expand(arr, map.get(l) - 1, r); // 继续递归扩展
        map.put(r - 1, l + 1); // (右, 左), ???这里为什么不在前面，测试时前后都不影响结果,到底为什么
        return r - 1;
    }

}