跳到主要内容

LeetCode 20. 有效的括号

本节目标

用栈顶保存最近未闭合的开放括号，验证嵌套括号是否完整匹配。

给定只含 ()[]{} 的字符串，判断括号是否有效。这里的有效不只是左右数量相同，还要求关闭顺序符合嵌套关系。这道题是栈与队列中“栈保存最近未完成状态”的母题。

查看原题

栈顶不变量​

从左到右扫描字符串，把开放括号压入栈。此时栈中保存的是已经出现、但还没有被关闭的开放括号；从栈底到栈顶，它们的出现时间越来越晚。

因此遇到关闭括号时，只有栈顶的开放括号可能与它配对。若栈为空，说明没有可匹配的开放括号；若类型不同，说明较晚出现的开放括号没有先闭合，例如 ([)]。

扫描规则​

对每个字符执行以下操作：

  1. 若是 (、[ 或 {，压入栈。
  2. 若是关闭括号，栈必须非空，且栈顶必须是对应的开放括号；匹配后弹出栈顶。
  3. 全部扫描完成后，栈为空才合法；否则仍有开放括号没有关闭。

映射关闭括号到其期望的开放括号，可以让三类括号共用同一段逻辑。

代码实现​

两种语言都只保存开放括号。Python 的字典把关闭括号映射到对应开放括号；C++ 在读到关闭括号时确定期望字符。平台接口分别为 bool Solution::isValid(string s) 与 Solution.isValid(self, s)。

C++17
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> opened;
        for (char ch : s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                opened.push(ch);
                continue;
            }

            char expected = ch == ')' ? '(' : (ch == ']' ? '[' : '{');
            // 栈顶必须匹配最近未闭合的括号
            if (opened.empty() || opened.top() != expected) {
                return false;
            }
            opened.pop();
        }
        return opened.empty();
    }
};

复杂度分析​

每个字符至多入栈、出栈一次，时间复杂度为 O(n)。最坏情况下字符串全是开放括号，栈空间为 O(n)。

易错点​

  • 只比较开放和关闭括号的数量：([)] 数量相同却不是合法嵌套。
  • 遇到关闭括号时没有先判断空栈，会访问不存在的栈顶。
  • 扫描结束后直接返回真：例如 "((" 仍有未闭合括号，应由最终空栈检查排除。

模式迁移​

只要题目要求处理嵌套、成对消去或“最近一个未完成状态”，都可以尝试把待处理对象放入栈。表达式求值、文件路径化简和单调栈问题都会继续使用这个栈顶优先的关系。