vvrf / DSA.log

问题拆解

给定一个只含 ()[]{} 的字符串，要判断括号是否正确闭合。合法有两个条件：类型要配对，顺序也要对。像 ([)] 三种括号数量都对，却因为交叉嵌套而非法。

我一开始想过“数一数每种括号左右是否相等”，但 ([)] 立刻推翻了这个想法——数量对不代表顺序对。真正的关键是：每遇到一个右括号，它必须闭合的是当前还没关闭的、离它最近的那个左括号。

“最近打开的必须最先关闭”，这句话本身就是栈的先进后出（LIFO）。

用栈匹配最近的左括号

把左括号一路压栈；遇到右括号时，栈顶就是“最近未闭合的左括号”，检查它们是否成对即可。我用一个字典把右括号映射到它期待的左括号，判断时更直接。

public boolean isValid(String s) {
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : s.toCharArray()) {
        if (!pairs.containsKey(ch)) {
            stack.push(ch);
        } else if (stack.isEmpty() || stack.pop() != pairs.get(ch)) {
            return false;
        }
    }
    return stack.isEmpty();
}

def isValid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for ch in s:
        if ch not in pairs:
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False

    return not stack

func isValid(s string) bool {
    pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
    stack := []byte{}
    for i := 0; i < len(s); i++ {
        ch := s[i]
        open, isClose := pairs[ch]
        if !isClose {
            stack = append(stack, ch)
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}

pub fn is_valid(s: String) -> bool {
    let mut stack = Vec::new();
    for ch in s.chars() {
        match ch {
            '(' | '[' | '{' => stack.push(ch),
            ')' => if stack.pop() != Some('(') { return false; },
            ']' => if stack.pop() != Some('[') { return false; },
            _   => if stack.pop() != Some('{') { return false; },
        }
    }
    stack.is_empty()
}

两个容易漏的边界：遇到右括号但栈是空的（没有左括号与之配对），直接判非法；遍历结束后栈必须为空，否则说明还有左括号没被关闭，比如 (((。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个字符进出栈各一次
空间	`O(n)`	最坏情况全是左括号，全部压栈

可以迁移的模式

需要处理“嵌套”“配对”“就近匹配”的结构；
当前的决策只依赖“最近一次未完成的操作”；
逆序回收：后进来的先被处理掉。

看到“成对”“嵌套”“最近的一个”，先想想能不能用栈把“最近”这件事管起来。