Longest Valid Parentheses leetcode

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

这道题要求的事最长有效的括号长度 而不是有效括号个数

用stack来完成, 但是stack内装括号所在的index 而不是括号本身, 遇到左括号就入栈 

遇到右括号就出栈并且判断当前序列是否最长. 

1.如果当前的栈是空的 那么久没有元素出栈 记录start的位置为 i + 1(右括号的下一位为有效起始位置)

2. 如果栈不空, 就弹出一个左括号, 2.1:弹出之后如果栈空了 则说明当前所有括号匹配 长度就是 i - start + 1;  2.2 如果当前栈不空, 则当前最大长度就是 i - (栈顶元素 + 1) + 1 = i - stack.peek()

时间复杂度O(n)

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int start = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    start = i + 1;//下一个位置为有效的起始位置
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        max = Math.max(max, i - start + 1);//因为要求长度 所以i - start 后面还要+1
                    } else {
                        max = Math.max(max, i - stack.peek()); // stack.peek()的下一位到i的距离是最大长度 因为栈内都是左括号 栈顶的下一位不可能是右括号
                    }
                }
            }
        }
        return max;
    }
}