[leetcode] 32. Longest valid bracket

32、 Longest valid bracket

subject ：

Give you one that only contains '(' and ')' String , Find the longest effective （ The format is correct and continuous ） The length of the bracket substring .

Example 1：

 Input ：s = "(()"
 Output ：2
 explain ： The longest valid bracket substring is  "()"

Example 2：

 Input ：s = ")()())"
 Output ：4
 explain ： The longest valid bracket substring is  "()()"

Example 3：

 Input ：s = ""
 Output ：0

Tips ：

0 <= s.length <= 3 * 10^4
s[i] by ‘(’ or ‘)’

Their thinking ：

For this bracket matching problem , Generally, stack is used

Let's first find all the index numbers that can match , Then find the longest continuous sequence ！

for example ：s = )(()()), We can find... With a stack ,

Location 2 And location 3 matching ,

Location 4 And location 5 matching ,

Location 1 And location 6 matching ,

This array is ：2,3,4,5,1,6 This is found through the stack , We sort in ascending order ！1,2,3,4,5,6

Find out that the length of the longest continuous sequence of the array is the longest effective bracket length ！

So the time complexity comes from sorting ：O(nlogn).

Next, let's think , Whether the sorting process can be omitted , When playing the stack ?

Look directly at the code and understand ! So the time complexity is ：O(n).

class Solution {
    
    public int longestValidParentheses(String s) {
    
        if (s == null || s.length() == 0) return 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        //System.out.println(stack);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
    
            if (s.charAt(i) == '(') stack.push(i);
            else {
    
                stack.pop();
                if (stack.isEmpty()) stack.push(i);
                else {
    
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}