题目: 最长有效括号

最长有效括号

难度：困难

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

 

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

 

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

分析

辅助栈

因为括号需要进行匹配，所以使用栈来辅助。

每次出栈统计一个计数，当没有左括号可以出栈的时候，本次计数达到最大值，然后从0开始重新计数。

题解

辅助栈

class Solution {
    public int solute(String s) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        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{
                    ans = Math.max(ans, i-stack.peek());
                }
            }
        }
        return ans;
    }
}