32. Longest Valid Parentheses

Link

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Solution

使用stack去把不能組合成parentheses 的index記下來。

[index0, index1 ... indexk]

這些index的間距之中的組合一定是可以合成parentheses。

只要計算其中 [0<->(index0-1)], [(index0+1)<->(index1-1)] ... [indexk+1 <=> maxLengh]的間距最大值即可。

 public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') stack.push(i);
            else{
                if(!stack.isEmpty() && s.charAt(stack.peek()) == '('){
                    stack.pop();
                }else{
                    stack.push(i);
                }
            }
        }
        int max = 0;
        int low = 0;
        int high = s.length();
        while(!stack.isEmpty()){
            low = stack.pop();
            max = Math.max(max, high - low - 1);
            high = low;
        }
        //計算從跟s.length到最大的index的差距
        max = Math.max(max, high);
           
        return max;
    }