题目

思路

一句话：遇到左括号就存起来，遇到右括号就检查「最近存进去的那个」是不是同类型。

最直白的想法是「消消乐」：反复删除相邻且同类型的闭合对 "()"、"[]"、"{}"，直到不能再删；如果最后删空了，就说明合法。

例如 "{[()]}"：先删 "()" 得 "{[]}"，再删 "[]" 得 "{}"，最后删 "{}" 得空串，返回 true。

这个方法直观又正确，但每一轮都要从头扫一遍；像 "((((...))))" 这种深嵌套串，每轮只能从最中间拆掉一层，最坏要扫 O(n) 轮，总时间退化成 O(n²)。

关键观察：遇到一个右括号时，它能不能闭合，只取决于「最近一个还没闭合的左括号」是不是同类型。这个“最近还没闭合、先来后走”的结构，正是后进先出——和「栈」天然匹配。

于是把扫描过程变成：左括号入栈；右括号和栈顶核对、配对成功就出栈；任何一步栈空或类型不匹配直接判 false；最后栈空才合法。

解法

用一个栈存放「尚未闭合的左括号」，栈顶永远是当前最内层的那个。

1. 建立映射 右括号 → 同类型左括号。
2. 扫描 s：遇到左括号就入栈；遇到右括号就检查「栈非空且栈顶等于映射值」，满足则出栈，否则返回 false。
3. 扫描结束后，栈为空返回 true，非空返回 false。

以 "{[()]}" 为例（栈按“底部 → 顶部”表示）：

扫描完且栈为空，因此合法。

下图把上面 3 个步骤串成流程，并逐步演示：

C++

class Solution {
public:
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。