Longest Valid Parentheses

lc 32

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.

想法1:

• 暴力解法，每次call isvalid 这个function

想法2:

• 用一个stack来记录，但是stack记录的是index的number，然后如果是“（”就入站，如果是“）”那么必须分两种情况，如果当前stack是空的，证明这个是一个无效的“）”“，这个符号以前的基本都是无效的，然后更新start的值，如果stack不为空，则pop出来，然后更新当前的max值，start不更行

public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null  || s.length() == 0) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        int start = -1;
        int max = 0;

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                if(stack.isEmpty()){
                    start = i;
                }else{
                    stack.pop();
                    int curt = stack.isEmpty() ? start :stack.peek();
                    max = Math.max((i - curt), max);
                }
            }
        }
        return max;
    }
}