32. Longest Valid Parentheses

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Example 1:

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

Example 2:

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

Example 3:

Input: s = ""
Output: 0

Constraints:

• $0 <= s.length <= 3 * 10^4$
• s[i] is ‘(‘, or ‘)’.

Code

) ( ) ( ) )
0 1 2 3 4 5

class Solution {
    public int longestValidParentheses(String s) {
        int res = 0;
        // push index
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            if(c == '('){
                stack.push(i);
            } else {
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        
        return res;
    }
}

使用了两个变量 left 和 right，分别用来记录到当前位置时左括号和右括号的出现次数， 当遇到左括号时，left自增1，右括号时right自增1。如果在某一时刻，左括号=右括号，那就一定是有效的字符串， 此时就可以更新结果了，一旦右括号数量超过左括号数量了， 说明当前位置不能组成合法括号子串，left 和 right 重置为0。

但是对于这种情况 “(()” 时，在遍历结束时左右子括号数都不相等， 此时没法更新结果，但其实正确答案是2，那么怎么处理这种情况呢？ 答案是再反向遍历一遍，采取类似的机制，稍有不同的是此时若left大于right了，则需要重置0

class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLen = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            
            if (left == right) {
                maxLen = Math.max(maxLen, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        
        left = right = 0;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            
            if (left == right) {
                maxLen = Math.max(maxLen, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxLen;
    }
}