🧠 括号栈 左括号入栈，右括号触发结算

⭐ 模板一 合法括号判断

  1. 左括号 → 入栈

  2. 右括号 → 弹栈并匹配

  3. 最后栈必须为空

    for (cahr c : s.toCharArray()){
    if ch 是左括号:
    入栈
    else:
    if 栈空: return false;
    top = 栈顶出栈;
    if top 与 c 不匹配:return false;
    }
    return 栈空;

⭐ 模板二 最长有效括号

  1. 遇到左括号，下标入栈

  2. 遇到右括号，当前遇到的 )，可以和栈顶的 ( 组成一对合法括号，于是把这个 ( 从栈里删掉。不能就更新最后的非法位置

    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{
    maxLen = Math.max(maxLen, i - stack.peek());
    }
    }
    }
    }
    return maxLen;

⭐模板三：需要删除多少括号

  1. 栈记录 未匹配的括号下标

  2. 最后统一删除这些位置

stack = []
invalid = set()

for i in range(len(s)):
    if s[i] == ‘(‘:
        stack.push(i)
    else if s[i] == ‘)’:
        if stack 非空:
            stack.pop()
        else:
            invalid.add(i)

把 stack 中剩余下标加入 invalid
删除 invalid 位置
换位Java的这种伪代码

⭐模板四：括号 + 字符串处理

  1. 栈处理 嵌套结构

  2. 每遇到 )，处理一段完整子串

stack = []
for ch in s:
if ch != ‘)’:
stack.push(ch)
else:
temp = “”
while stack.top() != ‘(‘:
temp += stack.pop()
stack.pop() // 弹 ‘(‘
把 temp 再压回栈

Notice:

  1. 合法括号判断为什么最后是返回栈为空

循环结束时，仅仅代表“没有发生冲突”，但不代表“所有括号都匹配完了”,栈为空，说明所有括号都匹配完了，没有发生冲突。

  1. 最长有效括号为什么要stack.push(-1)

栈里保存的是合法括号的下标，初始时，栈里应该有一个-1，这样，栈里第一个元素就是合法括号的左边界，栈里最后一个元素就是合法括号的右边界。

相关练习题

1. LeetCode 20. 有效的括号

题意： 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

2. LeetCode 32. 最长有效括号

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

3. LeetCode 921. 使括号有效的最少添加

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

4. LeetCode 1249. 移除无效的括号

题意： 给你一个由 ‘(‘、’)’ 和小写字母组成的字符串 s 。你需要从字符串中删除 最少数目的 ‘(‘ 或者 ‘)’ ，使得剩下的字符串有效。

5. LeetCode 1190. 反转每对括号间的子串

题意： 给出一个字符串 s（仅含有小写英文字母和括号）。返回 s 中 “反转字符串” 后的结果。括号中的内容需要翻转。