32. Longest Valid Parentheses

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

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1 2	Input: s = "" Output: 0

import java.util.*;
// TC: O(n), SC: O(n)  
class Solution {
    static public int longestValidParentheses(String s) {
        int ans = 0;  // number of pair
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // O(1), if not (, pop will cause EmptyStackException

        for(int i = 0; i< s.length(); i++){ // O(n)
            char ch = s.charAt(i); // O(1)
            if(ch == '('){
                stack.push(i); // O(1)
            }else{
                stack.pop(); // O(1)
                if(stack.size() == 0){
                    stack.push(i);
                }else{
                    ans = Math.max(ans,i- stack.peek());
                }
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        int ret = longestValidParentheses(")()())");
        System.out.println(ret);
    }
}

>
4

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)