32. Longest Valid Parentheses

class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left += 1;
            } else {
                right += 1;
            }
            if (left == right) {
                max = Math.max(max, left * 2);
            } else if (left < right) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left += 1;
            } else {
                right += 1;
            }
            if (left == right) {
                max = Math.max(max, left * 2);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return max;
    }
}

可以这么想. 我们只有在left == right的时候才能捕捉到某个substring, 此时的右括号的个数抵消了左边所有的左括号. 这里的所有的定义需要解释一下. 如果我们在某个时刻右括号数量大于了左括号, 那么可以认为该右括号把string一分为二. longest valid parentheses肯定不会跨越这两个string. 因此我们这里的左边所有括号指的是当前部分该位置左边所有的左括号, 并非整个string该位置左边的所有左括号. 但是有可能左括号一直比右括号多, 我们从而捕捉不到一些可能成为最长的答案. 这意味着, 在longest出现的部分到整个string遍历结束, 每个位置的left都是大于right的. 那么我们反向遍历即可. 假设longest起始是i, 终止是j. 那么在[i, j]所在的部分(见我们之前如何规定不同部分的), 每个位置的left都大于right, 那么我们反向遍历的时候, 肯定在i或i之后某个位置左括号大于右括号数量. 我们在到达j前, 此时right可能大于left, 可能等于left, 也可能小于. 如果小于, 那到j这里等于重新开始了新的部分, j右边的string被划分开了, 因为j右边right小于left, right不够分了. 我们在这里reset left和right. 如果left == right, 那么我们就可以捕捉到[i, j]. 如果right大于left, 那我们也能捕捉到, 因为i左边肯定有个时刻我们是left大于right的.

综上, 最长的string就捕捉到了.

时间复杂度: O(n)
空间复杂度: O(n)