每天一道算法题

LeetCode第32题：最长有效括号

这道题首先肯定能想到要使用栈来解决，但是这里容易陷入一个误区就是栈里放入的值，如果还是放括号本身的话那栈里的值相当于没有意义，因为本题里括号类型只有一种。所以这里充分利用栈，那么栈里就存最早一个(之前的下标，当出现匹配的右括号)时则可以计算长度，如后续出现不匹配则重新推入栈内新的初始下标即可。

/**
     * 解法一，栈里放括号下标，匹配后都计算当前最长有效括号
     */
    public static int longestValidParentheses(String s) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        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 {
                    // 移除后当前的最长串为 当前下标i减去移除后的上一个左括号下标
                    ans = Math.max(ans, i - stack.peek());
                }
            }
        }
        return ans;
    }

这里额外提供另一种官方提供的比较巧妙的解法，可以看看这个思想

/**
     * 解法二
     * 记录左右括号数量，遍历过程中只要出现右括号大于左括号数量如:())，则代表非有效括号数量归0。否则左右相等时表示当前有效记录长度
     * 后面一次循环是为了处理 (()() 这种左括号永远多于右括号的场景，次场景上次遍历中无法得出结果，所以反向遍历一次。
     */
    public static int longestValidParentheses2(String s) {
        int left = 0;
        int right = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                ans = Math.max(ans, 2 * left);
            } else if (right > left) {
                left = 0;
                right = 0;
            }
        }

        left = 0;
        right = 0;
        for (int i = s.length() - 1; i > 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                ans = Math.max(ans, 2 * left);
            } else if (left > right) {
                left = 0;
                right = 0;
            }
        }

        return ans;
    }