10._最长有效括号

• 2.19
  • 栈+贪心思想
  • 是左就入栈，不是就出栈，并判断是否为空

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

• 2.4
  • 栈解法，栈内存的是括号下标
    • 是左括号 push，是右括号弹出，看是不是空，
      • 空的话放进这个下标作为新的参照物，不是空的话，计算最大长度

import java.util.Stack;
 
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        // 1.放入一个初始参照物，处理边界情况
        // 比如 "()"，i=1时，1 - (-1) = 2
        stack.push(-1); 
        
        int maxLen = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (c == '(') {
                // 2. 左括号：只管存下标
                stack.push(i);
            } else {
                // 3. 右括号：先弹出栈顶
                stack.pop();
                
                if (stack.isEmpty()) {
                    // 如果栈空了，说明刚才弹出的那个东西是参照物（或者说这个 ) 没匹配到）
                    // 这个位置变成了新的“断点”，压入作为新的参照物
                    stack.push(i);
                } else {
                    // 如果栈不空，说明刚才弹出的左括号和现在的 ) 匹配成功
                    // 当前有效长度 = 当前位置 - 栈顶剩下的那个元素位置
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}