32. Longest Valid Parentheses

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.

思路：先把路径上配对的消掉，记下没消掉的位置。厉害

public class Solution {
    public int longestValidParentheses(String s) {
        int longest = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<Integer>();

        for (int i=0;i<s.length();i++){
            if (s.charAt(i)=='('){
                stack.push(i);
            }else{
                if (stack.empty()){
                    stack.push(i);
                }else if (s.charAt(stack.peek())=='('){
                    stack.pop();
                }else{
                    stack.push(i);
                }
            }
        }
        if (stack.empty()){
            return s.length();
        }

        int right = s.length();
        int left = 0;
        while(!stack.empty()){
            left = stack.pop();
            longest = Math.max(longest,right-left-1);
            right = left;
        }
        longest = Math.max(longest, left);
        return longest;
    }
}