November 22, 2019

32. Longest Valid Parentheses

Use stack, one pass. Time = O(n).

Valid Parentheses 不能隔断。而隔断有可能是左括号的出现，已经多余的右括号。
参考了这个视频讲解。

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        int n = s.length();
        int max = 0;
        int leftMost = -1;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                stack.offerFirst(i);
            } else {
                if (stack.isEmpty()) {
                    leftMost = i;
                } else {
                    int j = stack.pollFirst();
                    if (stack.isEmpty()) {
                        max = Math.max(max, i - leftMost);
                    } else {
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }
        }
        return max;
    }
}