算法刷题系列（十九）：括号问题——用栈与前缀约束检查

算法刷题系列（十九）：括号问题——用栈与前缀约束检查

栈篇介绍了后进先出的结构，表达式计算也用栈管理待处理状态。本篇把栈应用到括号：最近遇到的未匹配左括号必须最先与右括号配对。

括号题有几个不同问题，不能混为一谈：

1. 多种括号是否完整匹配；
2. 只有圆括号时，最长有效连续子串有多长；
3. 如何根据题目规则生成括号组合。

本文重点解决前两类，并解释它们分别依赖的状态。

一、多类型括号匹配：栈保存未闭合项

扫描字符串时：

• 遇到左括号，把它压入栈；
• 遇到右括号，检查栈顶是否为对应类型；
• 类型不一致或栈为空，立即判定不合法；
• 扫描结束后，栈必须为空。

栈顶是最近尚未闭合的左括号，因此嵌套结构能按后进先出的顺序匹配。

例如：

{[()]}  合法
{[(])}  不合法：遇到 ] 时，最近未闭合的是 (

二、Java：多类型括号检查

import java.util.ArrayDeque;
import java.util.Deque;

public class Parentheses {
    public static boolean isBalanced(String text) {
        if (text == null) {
            throw new IllegalArgumentException("text must not be null");
        }

        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < text.length(); i++) {
            char current = text.charAt(i);
            if (current == '(' || current == '[' || current == '{') {
                stack.push(current);
            } else if (current == ')' || current == ']' || current == '}') {
                if (stack.isEmpty() || !matches(stack.pop(), current)) {
                    return false;
                }
            } else {
                throw new IllegalArgumentException(
                    "text may contain only bracket characters"
                );
            }
        }
        return stack.isEmpty();
    }

    private static boolean matches(char opening, char closing) {
        return (opening == '(' && closing == ')')
            || (opening == '[' && closing == ']')
            || (opening == '{' && closing == '}');
    }
}

三、Python：多类型括号检查

def is_balanced(text: str) -> bool:
    if text is None:
        raise ValueError("text must not be None")

    pairs = {")": "(", "]": "[", "}": "{"}
    openings = set(pairs.values())
    stack: list[str] = []
    for char in text:
        if char in openings:
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
        else:
            raise ValueError("text may contain only bracket characters")
    return not stack

assert is_balanced("{[()]}")
assert not is_balanced("{[(])}")
assert not is_balanced("(()")
assert is_balanced("")

时间复杂度为 O(n)，最坏额外空间为 O(n)。

四、最长有效圆括号：栈记录边界

多类型匹配问的是整串是否合法；最长有效圆括号问的是某个连续子串的最长长度。这里有一个方便的栈技巧：栈存索引，并始终用栈顶表示当前有效段的左边界之前一个位置。

初始化栈为 [-1]。扫描到左括号就压入索引；扫描到右括号则弹出：

• 若栈空，把当前右括号索引压入，作为下一段的边界；
• 若栈不空，当前有效长度为 i - stack[-1]。

例如 ()(()：最后一个右括号边界使前一段不能跨越不匹配的位置。

五、Java：最长有效圆括号

import java.util.ArrayDeque;
import java.util.Deque;

public class LongestValidParentheses {
    public static int longestValidParentheses(String text) {
        if (text == null) {
            throw new IllegalArgumentException("text must not be null");
        }

        Deque<Integer> indices = new ArrayDeque<>();
        indices.push(-1);
        int best = 0;
        for (int i = 0; i < text.length(); i++) {
            char current = text.charAt(i);
            if (current == '(') {
                indices.push(i);
            } else if (current == ')') {
                indices.pop();
                if (indices.isEmpty()) {
                    indices.push(i);
                } else {
                    best = Math.max(best, i - indices.peek());
                }
            } else {
                throw new IllegalArgumentException(
                    "text may contain only '(' and ')'"
                );
            }
        }
        return best;
    }
}

六、Python：最长有效圆括号

def longest_valid_parentheses(text: str) -> int:
    if text is None:
        raise ValueError("text must not be None")

    indices = [-1]
    best = 0
    for index, char in enumerate(text):
        if char == "(":
            indices.append(index)
        elif char == ")":
            indices.pop()
            if not indices:
                indices.append(index)
            else:
                best = max(best, index - indices[-1])
        else:
            raise ValueError("text may contain only '(' and ')'")
    return best

assert longest_valid_parentheses(")()())") == 4
assert longest_valid_parentheses("(()") == 2
assert longest_valid_parentheses("") == 0

七、容易忽略的前提

最长有效圆括号的索引栈算法只适用于输入由 ( 和 ) 构成的字符串。多种括号混合时，不能只靠这个单栈边界公式求最长子串；需要根据题目定义重新设计状态。

常见错误：

1. 只统计左右括号总数相等：)( 总数相等，但并不合法。
2. 多种括号只记录数量：类型和嵌套顺序也必须正确。
3. 忘记初始边界 -1：会漏掉从字符串开头开始的有效段。
4. 遇到无法匹配的右括号后不重设边界：后面的有效段长度会跨过错误位置。
5. 把整串匹配与最长子串混为一题：两者的返回目标和维护状态不同。

小结

多类型括号匹配用栈顶匹配最近的未闭合左括号；最长有效圆括号可用索引栈维护有效段边界。明确题目是“整串是否合法”还是“最长连续合法片段”，再选择合适的不变量。