Skip to content

leetcode-20-valid-parentheses.md

Latest commit

 

History

History
184 lines (133 loc) · 6.44 KB

leetcode-20-valid-parentheses.md

File metadata and controls

184 lines (133 loc) · 6.44 KB
Raw

LeetCode 20. 有效的括号 (Valid Parentheses)

难度：Easy　|　标签：栈、字符串　|　栈入门必刷 ⭐⭐⭐

一、题目

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

有效字符串需满足：

  1. 左括号必须用 相同类型 的右括号闭合。
  2. 左括号必须以 正确的顺序 闭合（最后开的最先关 → 后进先出）。

约束

  • 1 <= s.length <= 10^4

示例

输入 输出
"()" true
"()[]{}" true
"(]" false
"([)]" false
"{[]}" true

题目链接：https://leetcode.cn/problems/valid-parentheses/

二、解题思路（学习重点）

1. 为什么是栈？

"最后开的最先关" = LIFO = 栈 的天然定义。

每遇到左括号入栈，遇到右括号时检查栈顶是否匹配：

  • 匹配 → 出栈，继续
  • 不匹配 / 栈空 → 直接 false

最后栈必须为空（所有左括号都被配对）。

学习点 ①："嵌套结构 / 匹配性问题" → 第一反应应是栈。如表达式求值、HTML/XML 校验、最长有效括号。

2. 优雅写法：把右括号入栈

遇左括号时入栈"它期望的右括号"，遇右括号时直接判等：

'(' → push ')'
'[' → push ']'
'{' → push '}'
其他 → pop 并与当前字符比较

这样比"判断三种左右配对"的 if-else 干净得多。

3. 容易踩的坑

坑 处理
用 Stack（同步开销大） 用 ArrayDeque<Character> 更快
遇到右括号前不判空 → pop 抛异常 先判 isEmpty() 返 false
字符串奇数长度还硬跑 可加剪枝：s.length() % 2 != 0 直接 false

三、Java 题解

解法 A：栈（推荐写法）

class Solution {
    public boolean isValid(String s) {
        if ((s.length() & 1) == 1) return false;  // 奇数必假
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }
}

记忆口诀：

"左来推右，右来比顶，最终栈空才算赢。"

解法 B：HashMap 维护配对关系（适合括号种类多）

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> pair = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!pair.containsKey(c)) {           // 是左括号
                stack.push(c);
            } else {
                if (stack.isEmpty() || stack.pop() != pair.get(c)) return false;
            }
        }
        return stack.isEmpty();
    }
}

四、复杂度

项 复杂度
时间 O(n)
空间 O(n) 栈最坏全是左括号

五、示例验证

s = "{[]}"

i c 栈（顶在右） 操作
0 { } push 期望的 }
1 [ } ] push ]
2 ] } 栈顶 ] == ] ✅ pop
3 } (空) 栈顶 } == } ✅ pop

栈空 → 返回 true ✅

s = "([)]"

i c 栈 操作
0 ( ) push
1 [ ) ] push
2 ) ) ] 栈顶 ] != ) → false

六、复盘与延伸

一句话总结

括号配对 = LIFO = 栈。左推右、右比顶、终须空。

新手常见疑问（FAQ）

Q1：为什么左括号要“推入它期待的右括号”而不是推入自己？ A：两者都能写。推“期待的右括号”能让右括号到来时直接 stack.pop() != c 一行判完，代码更短；推自己需要表查配对关系。

Q2：为什么不用 Stack，要用 ArrayDeque？ A：JDK 的 Stack 继承 Vector，所有方法都是 synchronized，有锁开销。ArrayDeque 无锁且为栈专设计，面试推荐。

Q3：成对计数能不能代替栈（如 (( 计 +1）？ A：不能。计数法会让 ([)] 这种 “括号数量对但顺序错” 的情况返回 true。栈才能护住“后进先出”。

Q4：为什么奇数长度可以提前返回 false？ A：有效括号一定是偶数个。提前判能省一遍扫描，微优化但是面试加分项。

Q5：字符串里含其他字符（如 "a(b)c"）怎么办？ A：跳过非括号字符即可，主结构不变。这也是 LC 1249 删除无效括号的基础。

面试官常见 follow-up

  1. "最长有效括号子串？" → 栈里存下标，配对后用 i - 栈顶下标 计长度。即 LC 32。
  2. "使括号有效的最少添加数？" → 扫一遍计数：左多了补右，右多了补左。即 LC 921。
  3. "删除最少括号使之有效？" → 栈记未配对的位置，扫二过跳过。即 LC 1249。
  4. "括号中含变量、表达式求值？" → 双栈法（数字栈 + 运算符栈）。类题：LC 224 / 227 / 772。
  5. "多种括号（含 <> 《》）可动态添加？" → 用 Map<Character, Character> 维护配对表，代码不变。
  6. "流式括号验证（字符一个个动态进来）？" → 同样用栈，上下文设计成服务类可以全程保持状态。

同类型推荐（栈家族）