有效的括号（栈）

目录

题目要求：

解法思路

复杂度

code

栈的理解

idea

🎬 括号匹配的动画想象

---

题目要求：

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

解法思路

使用栈数据结构：

1. 遍历字符串的每个字符。

2. 如果是左括号（(、[、{），压入栈。

3. 如果是右括号，检查栈顶的左括号是否与之匹配：

   • 若栈为空 → 无效（右括号多余）

   • 栈顶括号不匹配 → 无效

   • 匹配 → 弹出栈顶元素，继续

4. 遍历完成后，如果栈为空 → 有效；否则无效（左括号多余）

复杂度

• 时间复杂度：O(n)，每个字符入栈或出栈一次。

• 空间复杂度：O(n)，最坏情况下全部左括号入栈。

code

/** * @param {string} s * @return {boolean} */ var isValid = function (s) { const arr = [] for (let i = 0; i < s.length; i++) { const c = s[i] if (c == '(' || c == '{' || c == '[') { arr.push(c) } else { if (!arr.length) return false const top = arr[arr.length - 1] if (top == '(' && c == ')' || top == '{' && c == '}' || top == '[' && c == ']') { arr.pop() // 出栈 } else { return false } } } return arr.length == 0 };

栈的理解

idea

栈就像一个弹簧单托盘餐架（自助餐厅里常见的那种）

1. 只有一个开口：只能在最上面放盘子或取盘子

2. 后进先出：最后放上去的盘子会最先被拿走

3. 只能看到最上面的盘子：不把上面的拿走，就拿不到下面的

在此题括号匹配问题中：

• 左括号👉放盘子（压栈push）

• 右括号👉取盘子（弹栈pop），但必须和刚放的盘子匹配类型

🎬 括号匹配的动画想象

以"({[]})"为例：

步骤1: "(" → 栈：[ "(" ] ↑ 步骤2: "{" → 栈：[ "(", "{" ] ↑ 步骤3: "[" → 栈：[ "(", "{", "[" ] ↑ 步骤4: "]" → 匹配栈顶"["，弹出 → 栈：[ "(", "{" ] ↑ 步骤5: "}" → 匹配栈顶"{"，弹出 → 栈：[ "(" ] ↑ 步骤6: ")" → 匹配栈顶"("，弹出 → 栈：[ ] ↑ 结束 → 栈空 ✅ 有效