每日一题-最长有效括号-0724

题目

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

思路

1. 括号匹配题目优先从栈的角度切入，本题中需要找到最长的括号子串的长度，通过数组的下标进行匹配
2. 优先入栈一个-1的下标，作为栈底的元素（保证栈不会空）
3. 遇到左括号的时候入栈，右括号的时候先弹出当前的栈顶元素，如果这个时候栈非空，证明之前入栈过左括号，满足括号对的前提要求；如果是空的，右括号的下标入栈，保证栈不会是空的，还有一点就是后面有满足要求的括号对的时候，作为栈顶下标元素计算当前子串的长度
4. 最后通过sum不断迭代，更新当前的最大值

代码

class Solution {
    
    public int longestValidParentheses(String s) {
    
        if(s == null || s.length() <= 0)
            return 0;
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        //站岗
        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{
    
                    sum = Math.max(sum, i - stack.peek());
                }
            }
        }
        return sum;
    }
}