# LeetCode 热题 100 — 知识地图与故事化讲解
先懂"为什么"，再去"怎么做"。这份指南用生活中的小故事帮你理解每类题目背后的核心思想。
# 目录
# 1. 哈希表 — 建一本万能字典
# 题目
| # | 题目 |
|---|---|
| 1 | 两数之和 |
| 49 | 字母异位词分组 |
| 128 | 最长连续序列 |
# 故事
想象你是一个图书管理员。有人问你："图书馆里有没有《三体》？"
笨办法：从第一个书架开始，一本一本翻，直到找到或翻完所有书。如果有10万本书，最坏情况要翻10万次。
聪明办法：你建了一本索引目录——按书名首字母排好，直接翻到"S"那一页，瞬间找到。
这就是哈希表的本质：用空间换时间，建立一个"查号簿"，让查找从 O(n) 变成 O(1)。
但哈希表在算法题里最妙的用法，不是"先建好索引再查"，而是边走边查。
想象你走进一间教室，要找两个学号加起来等于100的同学。笨办法是让每个人跟所有人配对试一遍——50个人就是1225种组合。但你可以换个思路：你从第一个同学开始，挨个走过去。走到学号37的同学面前，你心想："我需要的搭档是63号，花名册上有63号吗？"翻一下——没有。那就把37号记到花名册上，继续往前走。走到63号面前："我需要37号，花名册上有吗？"有！配对成功。
你走过的人越多，花名册越厚，后面的人越容易找到搭档。一次遍历就够了——每个人只被看一次，每次查花名册是 O(1)，总共 O(n)。这就是"两数之和"的核心思路：不是先把所有人登记完再配对，而是走到哪，查到哪，记到哪。
# 核心思想
问题：在一堆东西里快速找到某个东西
暴力：逐个比较 → O(n)
哈希：先存到字典里，直接查 → O(1)
2
3
哈希表就像你手机里的通讯录：
- 存：把"张三 → 13800138000"记进去
- 查：想找张三的电话？不用翻遍所有联系人，直接搜"张三"
# 解题模式
当你看到题目里有这些关键词时，考虑哈希表：
- "找到两个数使得……" → 边遍历边查字典
- "分组" → 用某个特征作为 key
- "是否存在" → 先存后查
- "去重" → 利用 set
# 2. 双指针 — 两个人合作比一个人快
# 题目
| # | 题目 |
|---|---|
| 283 | 移动零 |
| 11 | 盛最多水的容器 |
| 15 | 三数之和 |
| 42 | 接雨水 |
# 故事
# 对撞指针：走廊里的两个人
想象一条长长的走廊，走廊两头各站着一个人——小左和小右。走廊里的柱子从左到右越来越高（已排序），他们要找两根柱子，高度加起来刚好等于某个目标值。
如果只有小左一个人，他得站在第一根柱子旁，让小右从头到尾走一遍；然后站到第二根柱子旁，再让小右走一遍……这是 O(n²) 的暴力。
但两个人一起就不一样了。小左从最矮的柱子出发，小右从最高的柱子出发：
- 两人各伸出一只手，加起来看看——太小了？说明小左这边不够高，小左往右挪一步，找根更高的
- 太大了？说明小右这边太高了，小右往左挪一步，找根矮一点的
- 刚好？找到了！
为什么不会错过答案？ 这是最关键的直觉——当两人的和太小时，小左当前这根柱子，不管跟走廊里哪根柱子配对，最大也就是跟小右（最高的那根）配，而这都不够大。所以小左这根柱子的所有配对都可以安全排除。小左不是在盲目地走，而是在说："我这根不行了，我的最佳搭档都不够，换一根。"
每一步都安全地排除了一整列可能性。两个人走过的步数加起来最多就是走廊长度——O(n)。
# 快慢指针：操场上的追逐
想象一个环形操场，小明和小红同时从起点出发。小明每秒走一步，小红每秒走两步。
如果操场是一条直线（没有环），小红会先跑到终点，两人不会相遇——这就证明了"没有环"。
但如果操场是环形的呢？小红跑得快，很快就"超过"小明一圈。但她不是瞬间超过的——每一秒，小红都比小明多走一步，两人的距离每秒缩小1。就像时钟上的秒针追分针，不管分针在哪，秒针每秒都在靠近，终究会追上。
所以：快慢指针相遇 = 有环。快指针走到头（遇到 null）= 无环。
# 同向指针：整理书架的两个人
想象你在整理一排书架，要把所有空格（零）移到最右边，其他书保持原顺序。
探路者从左往右翻看每一格：遇到一本书？递给身后的整理者，整理者把书放在下一个空位上。遇到空格？跳过。
探路者走得快，整理者走得慢。等探路者走完整排书架，整理者后面全是空位。两个人朝同一个方向走，但速度不同——快的负责发现，慢的负责安置。
# 核心思想
一个指针太慢？用两个！
- 对撞指针：从两端向中间收缩，适合有序数组
- 快慢指针：一快一慢，适合链表、找环、找中点
- 同向指针：一个走得快，一个走得慢，用于分区/移除
2
3
4
# 解题模式
- 数组已排序 + 找配对 → 对撞指针
- 链表找环 / 找中点 → 快慢指针
- 原地移除/分区 → 同向双指针（一个读，一个写）
# 3. 滑动窗口 — 尺蠖虫的智慧
# 题目
| # | 题目 |
|---|---|
| 3 | 无重复字符的最长子串 |
| 438 | 找到字符串中所有字母异位词 |
| 560 | 和为 K 的子数组 |
| 239 | 滑动窗口最大值 |
| 76 | 最小覆盖子串 |
# 故事
想象你在看一本很长的书，要找到最短的一段话，这段话里包含了"勇气"、"智慧"、"友情"这三个词。
笨办法：检查每一种可能的起止位置组合。如果书有1000页，那就是近50万种组合。
聪明办法：像一条尺蠖虫一样蠕动前进——
- 先伸长身体（右端向右扩展），直到这段话包含了所有三个词
- 然后缩短身体（左端向右收缩），看能不能更短还满足条件
- 记录下满足条件的最短长度
- 缩过头了（某个词掉出去了）？继续伸长右端，找到新的包含所有词的段落
为什么左端永远不用往回走？ 这是滑动窗口最反直觉的地方。想象左端曾经停在第5页，右端伸到第20页才凑齐三个词。那以第5页为起点的最短有效段就是5~20。然后左端右移到第6页，发现"勇气"掉出去了，于是右端继续往右找新的"勇气"。
这时候你需要把左端退回第5页吗？不需要。因为以第5页为起点的最优答案你已经记下来了——就是刚才的5~20。以第4页、第3页为起点的最优答案也早就记过了。左端走过的地方，最优答案已经尘埃落定，没有回头的理由。
所以左端和右端都只向右走，永远不回头。两个端点加起来最多各走 n 步——整个过程 O(n)。
# 核心思想
维护一个[left, right]的窗口：
- 不满足条件 → right 右移，扩大窗口
- 满足条件 → left 右移，缩小窗口，尝试找更优解
- 整个过程 left 和 right 都只向右移动 → O(n)
2
3
4
# 解题模式
- "最长/最短的连续子串/子数组，满足某条件" → 滑动窗口
- 关键词：连续、子串、子数组、最长/最短
# 4. 普通数组 — 在限制中寻找巧思
# 题目
| # | 题目 |
|---|---|
| 53 | 最大子数组和 |
| 56 | 合并区间 |
| 189 | 轮转数组 |
| 238 | 除自身以外数组的乘积 |
| 41 | 缺失的第一个正数 |
# 故事
这类题有个共同特点：带着镣铐跳舞——不能用额外空间（O(1)空间），或者不能用某个操作（不能用除法），你得在限制中想出巧妙的办法。
比如"轮转数组"：把 [1,2,3,4,5,6,7] 右移3位变成 [5,6,7,1,2,3,4]。
想象一支队伍排成一排，你想让最后3个人站到最前面去。直接一个个搬？太麻烦。但有个魔术般的办法——
- 所有人向后转（整体翻转）：
[7,6,5,4,3,2,1] - 前3个人内部再转回来：
[5,6,7,4,3,2,1] - 后4个人内部再转回来：
[5,6,7,1,2,3,4]
为什么有效？整体翻转把最后3个人"甩"到了前面，但顺序反了。局部翻转把顺序修正回来。整体翻转摆对位置，局部翻转修正顺序——两步配合，原地完成。
# 核心思想
常见技巧：
- 前缀和：预处理累加和，快速求任意区间的和
- 原地操作：用翻转、交换代替额外空间
- 排序预处理：排序后很多问题变简单（如合并区间）
- 利用数组索引：把值当索引用，原地标记
2
3
4
5
# 5. 矩阵 — 在二维世界里导航
# 题目
| # | 题目 |
|---|---|
| 73 | 矩阵置零 |
| 54 | 螺旋矩阵 |
| 48 | 旋转图像 |
| 240 | 搜索二维矩阵 II |
# 故事
矩阵就是一张棋盘。你在上面要做的事情无非三种：
遍历——螺旋矩阵就像蜗牛爬行：沿着外圈走一圈，走完了往里缩一圈，再走一圈……你需要维护上下左右四堵"墙"，每走完一条边就把那堵墙往里推一格。墙越来越近，圈越来越小，直到墙碰墙，蜗牛走完了。
变换——旋转图像90度，直觉上很难"原地旋转"。但有个两步走的巧思：先沿对角线翻折（转置），再左右镜像翻转。就像你把一张纸先沿左上到右下的对角线折一下，再沿中线翻——纸上的内容就旋转了90度。两步都是原地操作，不需要额外空间。
搜索——搜索二维矩阵最聪明的起点是右上角。站在右上角你拥有一个特殊的能力：往左走数字变小，往下走数字变大。你就站在一个天然的十字路口——目标比你大？左边全比你小，更不可能，只能往下走，一步排除一整行。目标比你小？下面全比你大，更不可能，只能往左走，一步排除一整列。每一步都在缩小包围圈，最多走 m+n 步就能找到答案或确认不存在。
# 核心思想
- 螺旋遍历：维护上下左右四个边界，一圈圈收缩
- 旋转90°= 转置 + 水平翻转
- 搜索有序矩阵：从右上角/左下角开始，每步排除一行或一列
- 原地标记：用矩阵自身的第一行/第一列做标记位
2
3
4
# 6. 链表 — 火车车厢的艺术
# 题目
| # | 题目 |
|---|---|
| 160 | 相交链表 |
| 206 | 反转链表 |
| 234 | 回文链表 |
| 141 | 环形链表 |
| 142 | 环形链表 II |
| 21 | 合并两个有序链表 |
| 2 | 两数相加 |
| 19 | 删除链表的倒数第 N 个结点 |
| 24 | 两两交换链表中的节点 |
| 25 | K 个一组翻转链表 |
| 138 | 随机链表的复制 |
| 148 | 排序链表 |
| 23 | 合并 K 个升序链表 |
| 146 | LRU 缓存 |
# 故事
链表就像一列火车——每节车厢只知道下一节车厢是谁，不知道前面有几节，也不知道自己是第几节。你没有上帝视角，只能从车头开始，一节一节往后走。
# 反转链表：把火车倒着开
你站在第1节车厢旁边，把它从链子上摘下来，放到地上——它现在是新火车的车头。走到第2节，摘下来，挂到第1节前面——现在第2节是车头。走到第3节，摘下来，挂到最前面……每一步都在把"下一节车厢"变成"新车头"。
关键动作只有一个：摘下来，挂到前面去。但是！摘下来之前，你得先记住"第3节在哪"，不然摘完第2节，你就找不到第3节了——这就是为什么链表操作总需要一个临时变量保存"下一个"。
# 检测环：龟兔赛跑
如果火车的最后一节车厢偷偷连回了中间某节，这列火车就形成了一个环。你站在车头，怎么知道前方有没有环？
让乌龟和兔子同时从车头出发。乌龟一次走一节车厢，兔子一次走两节。
如果没有环，兔子会先走到尽头（遇到 null），回来报告："路是直的，没有环。"
如果有环，兔子会先进入环里绕圈，乌龟随后也进入环。现在两人都在环里了——兔子每一步都比乌龟多走一节，两人的间距每一步缩小1。不管环有多大、兔子领先多少，距离在一步步缩小，终究会变成0——也就是相遇。
更妙的是找到环的入口。相遇后，让一人回到车头，两人都改成每次走一步。他们会在环的入口再次相遇。为什么？假设车头到环入口距离是 a，环入口到相遇点距离是 b，相遇点回到环入口距离是 c。相遇时乌龟走了 a+b，兔子走了 a+b+c+b（多绕了一圈），而兔子走的是乌龟的两倍：2(a+b) = a+2b+c，化简得 a = c。车头到入口的距离 = 相遇点到入口的距离——所以两个人各走一步，恰好在入口碰面。
# 相交链表：最浪漫的算法
两条路从不同的地方出发，在某处汇合，之后合为一条路。你站在 A 路的起点，朋友站在 B 路的起点，你们怎么找到那个汇合点？
一个美到令人心碎的解法——走完自己的路，再走一遍对方的路。
A 的路：独行 a 步，共行 c 步。B 的路：独行 b 步，共行 c 步。
你从 A 出发，走完 a+c 步到了尽头，然后转到 B 的起点继续走。朋友从 B 出发，走完 b+c 步到了尽头，然后转到 A 的起点继续走。
你走的总路程：a + c + b。朋友走的总路程：b + c + a。
一样长。 你们一定会在某一步同时到达同一个地方——那就是汇合点。不需要量路长，不需要做标记，只需要走过彼此走过的路。
如果两条路根本没有交汇呢？你走了 a+b 步，朋友也走了 b+a 步，同时到达虚无（null）。在空无中相遇，确认了彼此的路没有交集——这也是一种回答。
# 核心思想
链表的核心操作就这几种：
1. 遍历：一个个往后走
2. 反转：改变指针方向
3. 快慢指针：找中点、检测环
4. 虚拟头节点（dummy）：简化边界处理
5. 合并：归并排序的思想
2
3
4
5
6
# 关键技巧
- 画图！画图！画图！ 链表题不画图容易把指针搞乱
- 用
dummy虚拟头节点可以避免讨论"头节点为空"等边界情况 - 改变指针之前，先用临时变量保存下一个节点
# 7. 二叉树 — 家族族谱的秘密
# 题目
| # | 题目 |
|---|---|
| 94 | 二叉树的中序遍历 |
| 104 | 二叉树的最大深度 |
| 226 | 翻转二叉树 |
| 101 | 对称二叉树 |
| 543 | 二叉树的直径 |
| 102 | 二叉树的层序遍历 |
| 108 | 将有序数组转换为二叉搜索树 |
| 98 | 验证二叉搜索树 |
| 230 | 二叉搜索树中第 K 小的元素 |
| 199 | 二叉树的右视图 |
| 114 | 二叉树展开为链表 |
| 105 | 从前序与中序遍历序列构造二叉树 |
| 437 | 路径总和 III |
| 236 | 二叉树的最近公共祖先 |
| 124 | 二叉树中的最大路径和 |
# 故事
二叉树就是一个家族族谱。每个人最多有两个孩子（左孩子、右孩子）。
# 递归：族长的智慧
递归是理解二叉树的钥匙。想象你是族长，有人问你："你的家族一共有多少代？"
你不需要亲自跑遍整个家族去数人头。你只需要分别问你的左孩子和右孩子："你们那边各有多少代？"然后取较大值加1就行了。你的孩子也不知道答案，于是他们又用同样的方式去问自己的孩子……一层层问下去，直到问到没有孩子的人（叶子节点），他回答"就我一个人，1代"。答案从最底层一层层汇报上来，最终汇聚到你这里。
这就是递归——你不需要知道整棵树长什么样，你只需要相信你的孩子会给你正确的答案，然后做好自己这一层的事。
# 层序遍历：点名册按辈分来
层序遍历像族谱的辈分点名。你不是递归地一条线追到底，而是一代一代地点名：先喊爷爷辈所有人的名字，再喊父辈所有人，再喊孙辈……
怎么做到？想象一个排队系统。一开始只有族长（根节点）排在队伍里。你把族长叫出来，记下名字，然后让他的两个孩子排到队尾。接着叫下一个人（族长的左孩子），记下名字，让他的孩子排到队尾……就这样，一代人出完队后，他们的孩子刚好全部排在队伍里，形成了下一代。队列天然保证了"同代人先出完，下一代再出"的顺序。
# 二叉搜索树：一本天然有序的族谱
二叉搜索树（BST）有个特殊规则：每个人的左孩子比自己小，右孩子比自己大。这个规则递归下去，整棵树就被"排好序"了。
但怎么把这个"有序"读出来？中序遍历——先访问左子树，再访问自己，最后访问右子树。想象你从族谱最左下角的人开始，一路按"左→根→右"的顺序走，读出来的名字恰好是从小到大排好的。这不是巧合，这是BST的定义决定的：左边都比我小，我比右边都小，所以按左→我→右的顺序读，天然有序。
这意味着很多"有序数组上的问题"可以在BST上用中序遍历解决——比如"第K小的元素"，就是中序遍历数到第K个就停。
# 最近公共祖先：左右各一个
有人问你："小A和小B的最近共同长辈是谁？"你是族长（根节点），你分别问左孩子和右孩子："你那边能找到小A或小B吗？"如果左边找到了一个、右边也找到了一个——说明他们分布在你的两侧，你就是那个把他们连在一起的人，你就是答案。如果两个人都在左边？那答案在左子树里，和你无关。你的左孩子会用同样的方式继续问他的孩子……递归下去，总有一个祖先恰好"左右各一个"——那就是最近的公共祖先。
# 核心思想
二叉树 90% 的题用这两种思路之一：
1. 递归/DFS：把问题拆解为"对左子树做 + 对右子树做 + 合并结果"
- 前序遍历（根→左→右）：适合自顶向下传递信息
- 中序遍历（左→根→右）：BST 中序就是有序的！
- 后序遍历（左→右→根）：适合自底向上汇总信息
2. BFS/层序遍历：用队列，一层一层处理
- 适合：层序输出、最短路径、右视图
2
3
4
5
6
7
8
9
# 8. 图论 — 地图探险家
# 题目
| # | 题目 |
|---|---|
| 200 | 岛屿数量 |
| 994 | 腐烂的橘子 |
| 207 | 课程表 |
| 208 | 实现 Trie（前缀树） |
# 故事
先说两种最基本的探索方式的区别——
DFS（深度优先） 像一个人走迷宫：选一条路一头扎进去，走到死胡同再回头换条路。它看到的世界是"一条线"。
BFS（广度优先） 像往湖里扔一块石头：水波一圈一圈往外扩散，第一圈是距离1的点，第二圈是距离2的点……它看到的世界是"一层层的同心圆"。这就是为什么 BFS 天然能求最短距离——水波第一次碰到目标时，一定是最短路径，因为更短的路径早就被更早的波纹覆盖了。
岛屿数量：想象你是飞行员，从高空俯瞰一片海域。你的任务是数清楚有几个独立的岛屿。策略是：从左上角开始扫描。每看到一块陆地，就往湖里扔一块石头（或者派一个人走迷宫）——让水波/探险家把整个岛淹没/走遍，走过的地方标记为"已探索"。等这个岛处理完了，继续扫描。再遇到未探索的陆地，又是一个新岛。你扔了几次石头，就有几个岛。DFS 和 BFS 都行，因为这里只需要"走遍"，不需要求最短距离。
腐烂的橘子：这道题就是 BFS 最纯粹的体现。不是一块石头扔进湖里，而是所有烂橘子同时扔进去——多个起点的水波同时扩散。第1分钟，所有烂橘子旁边的好橘子被传染（第一圈水波）；第2分钟，新烂掉的橘子又向外传染一圈（第二圈水波）……为什么不能用 DFS？因为 DFS 是一个人走迷宫，它会沿着一条路传染到底再回头，这样算出来的"分钟数"不对——传染是同时发生的，而 BFS 的"一圈一圈扩散"恰好模拟了这种同时性。
课程表：有些课有先修要求（学B之前必须先学A）。这就是拓扑排序——像大学排课一样，必须保证先修课在前面。如果出现循环依赖（A要求先学B，B又要求先学A），就不可能修完所有课。
前缀树 Trie：想象一本字典，所有以"app"开头的词（apple, application, approve）共享前缀"app"这条路径。Trie 就是这样一棵共享前缀的树，搜索效率极高。
# 核心思想
- DFS（深度优先）：一条路走到黑，走不通再回头 → 适合"探索连通区域"
- BFS（广度优先）：像水波一样一圈圈扩散 → 适合"最短距离/时间"
- 拓扑排序：有向无环图中，按依赖关系排序
- Trie：利用共享前缀高效存储和查询字符串
2
3
4
# 9. 回溯 — 走迷宫的勇者
# 题目
| # | 题目 |
|---|---|
| 46 | 全排列 |
| 17 | 电话号码的字母组合 |
| 39 | 组合总和 |
| 22 | 括号生成 |
| 79 | 单词搜索 |
| 131 | 分割回文串 |
| 51 | N 皇后 |
# 故事
回溯就是走迷宫——但关键不是"往前走"，而是"怎么退回来"。
想象你在迷宫里用粉笔画箭头标记走过的路。走到岔路口，你选了左边那条路，一路画箭头往前走。走到死胡同——怎么办？你不能留着箭头不管就跑去试另一条路，因为那些箭头是你"当前路径"的一部分。你必须一边往回走，一边擦掉刚画的箭头，回到岔路口，让状态干干净净地恢复到你做选择之前的样子。然后再选右边那条路，重新画箭头往前走。
如果不擦箭头会怎样？你走右边那条路时，身上还带着左边路的痕迹——你记录下来的"路径"里混进了不该有的东西。撤销选择就是擦掉粉笔印，这是回溯的灵魂。
N 皇后是最经典的例子：在 N×N 棋盘上放 N 个皇后，使她们互不攻击。你一行一行地放：
- 第1行：试着放在第1列，画一个箭头（记录选择）
- 第2行：试着放在每一列，找到不冲突的位置
- 如果某一行怎么都放不下 → 擦掉上一行的箭头（撤销选择），回到上一行换个位置重试
# 核心思想
def backtrack(路径, 选择列表):
if 满足结束条件:
收集结果
return
for 选择 in 选择列表:
做选择 # 把选择加入路径
backtrack(路径, 选择列表) # 递归
撤销选择 # 把选择从路径移除（回溯的关键！）
2
3
4
5
6
7
8
9
# 解题模式
- 排列问题：顺序有关，用 visited 数组标记
- 组合问题：顺序无关，用 start 索引避免重复
- 切割问题：类似组合，切割位置就是选择
- 棋盘问题：逐行放置，检查约束
# 10. 二分查找 — 猜数字游戏的最优策略
# 题目
| # | 题目 |
|---|---|
| 35 | 搜索插入位置 |
| 74 | 搜索二维矩阵 |
| 34 | 在排序数组中查找元素的第一个和最后一个位置 |
| 33 | 搜索旋转排序数组 |
| 153 | 寻找旋转排序数组中的最小值 |
| 4 | 寻找两个正序数组的中位数 |
# 故事
小明心里想了一个 1~100 的数字，你来猜。每次猜完小明会告诉你"大了"还是"小了"。
最笨的方法：从1猜到100，最多猜100次。 最聪明的方法：先猜50——大了就在1~49里找，小了就在51~100里找。每次猜中间的数，一次排除一半，最多7次就能猜到（log₂100 ≈ 7）。
这就是二分查找：每次把搜索范围砍一半。它的前提是某种意义上的有序——你能根据中间位置的信息，判断答案在左半边还是右半边。
旋转排序数组是二分查找最有趣的变体。想象一副排好顺序的扑克牌 [0,1,2,4,5,6,7]，你从中间切一刀，把后半摞放到前面：[4,5,6,7,0,1,2]。整体不有序了，但你看中间的那张牌（5），左半边 [4,5,6,7] 是有序的，右半边 [0,1,2] 也是有序的——至少有一半是有序的。
这就是关键洞察。你先判断哪半边有序（比较 mid 和两端就知道），然后看目标值是否落在有序的那半边的范围内。如果落在里面，就去有序的那半边找（这是普通的二分查找）；如果不在，就去另一半找（那半边虽然也被"切"过，但同样的逻辑递归适用）。每一步仍然能排除一半——即使牌被切乱了，二分的力量依然有效。
# 核心思想
前提：某种意义上的"有序"（或能判断答案在哪一半）
while left <= right:
mid = (left + right) // 2
if 找到了: return mid
if 应该往右找: left = mid + 1
else: right = mid - 1
2
3
4
5
6
7
# 难点
二分查找的核心不难，难在边界处理：
left <= right还是left < right？right = mid还是right = mid - 1？- 找的是精确值、左边界、还是右边界？
建议：选一套模板，彻底弄懂，然后一直用它。
# 11. 栈 — 叠盘子的哲学
# 题目
| # | 题目 |
|---|---|
| 20 | 有效的括号 |
| 155 | 最小栈 |
| 394 | 字符串解码 |
| 739 | 每日温度 |
| 84 | 柱状图中最大的矩形 |
# 故事
栈就像食堂里叠起来的盘子——最后放上去的盘子，最先被拿走（后进先出，LIFO）。这个简单的性质，恰好是处理"嵌套结构"的利器。
# 括号匹配：放盘子与收盘子
想象你在检查公式 ((a+b)*(c-d)) 的括号是否匹配。你从左往右读：遇到左括号 ( 就放一个盘子，遇到右括号 ) 就拿走一个盘子。如果每次拿走的盘子都和右括号匹配，最后盘子全拿完了——匹配！如果中途想拿盘子但没有了，或者读完后还有盘子剩着——不匹配。
为什么栈在这里有效？因为括号是嵌套的——最后打开的括号，一定最先关闭。这正好是"后进先出"。
# 字符串解码：栈的嵌套魔法
3[a2[c]] 该解码成什么？accaccacc。
关键难点是嵌套——2[c] 在 3[...] 里面，你必须先解开里面的，再处理外面的。这又是"最后遇到的最先处理"——栈的主场。
想象你在拆一个套娃。你从左往右读，遇到数字和 [ 就把当前的"上下文"（已经拼好的字符串和重复次数）推进栈里，开始一个新的空白上下文。遇到 ] 就把最近的套娃拆开：取出栈顶的上下文，把当前拼好的字符串重复相应次数，拼接到上层上下文后面。
每遇到一个 [，就像打开一个新套娃；每遇到一个 ]，就像合上一个套娃并放回外层。栈替你记住了"外面还有几层套娃没合上"。
# 单调栈：排队看电影
想象你排队进电影院，每个人只关心一个问题：我后面第一个比我高的人是谁？
你身高 170，你前面站着 165、160、155。他们都比你矮——现在你来了，他们的问题瞬间有了答案："后面第一个比我高的人就是你（170）！"于是他们开心地离开队伍，你站到了最前面。
单调栈做的就是这件事：维护一个从栈底到栈顶递减的序列。新来一个人，把前面所有比自己矮的人"弹出去"——弹出的那一刻，就是告诉他们"你等的那个更高的人来了"。弹完后，自己站到栈顶。
为什么这行得通？因为被弹出去的人已经被"挡住"了——你比他们高，站在他们后面，以后不管谁来，都看不到他们，只能看到你。他们已经没有存在的价值了，所以可以安全弹出。
# 核心思想
普通栈：
- 匹配问题（括号、标签）→ 左半部分入栈，遇到右半部分就弹出匹配
- 嵌套结构（字符串解码）→ 遇到嵌套开始就压栈，结束就弹栈
单调栈：
- "下一个更大/更小的元素" → 维护单调递减/递增的栈
- 本质：高效地找到每个元素左边/右边第一个比它大/小的元素
2
3
4
5
6
7
# 12. 堆 — VIP 优先通道
# 题目
| # | 题目 |
|---|---|
| 215 | 数组中的第 K 个最大元素 |
| 347 | 前 K 个高频元素 |
| 295 | 数据流的中位数 |
# 故事
想象一个医院的急诊室。病人不是按到达顺序看病的，而是谁病得最严重谁先看——这就是优先队列/堆。
- 最大堆：最"大"的元素在堆顶（VIP 先出来）
- 最小堆：最"小"的元素在堆顶
第 K 大元素：找第K大，直觉上应该用最大堆？恰恰相反——用最小堆。
想象一个只能坐K个人的VIP包厢，门口坐着包厢里最弱的人（最小堆的堆顶就是最小值）。新来一个人，跟门口的比：比门口的强？门口那个请出去，你进来。比门口的弱？你连包厢里最弱的都不如，请回吧。
这样，包厢里始终是到目前为止最强的K个人。而门口那个——包厢里最弱的——恰好就是第K强的。用最大堆你得维护所有人；用最小堆你只需要维护K个人，多余的自动被淘汰。
数据流的中位数：用两个堆——一个最大堆存较小的一半，一个最小堆存较大的一半。就像把一副扑克牌分成两半，左手拿小的（朝上放最大的），右手拿大的（朝上放最小的），两只手顶上的牌就是中间位置的牌。中位数随时可以 O(1) 算出来。
# 核心思想
堆的核心价值：在动态变化的数据中，快速取得最大/最小值
- 插入: O(log n)
- 取最值: O(1)
- 删除最值: O(log n)
2
3
4
# 13. 贪心算法 — 活在当下的策略
# 题目
| # | 题目 |
|---|---|
| 121 | 买卖股票的最佳时机 |
| 55 | 跳跃游戏 |
| 45 | 跳跃游戏 II |
| 763 | 划分字母区间 |
# 故事
贪心就是只看眼前，每一步都选当前最好的，希望最终结果也是最好的。听起来很天真——凭什么局部最优就能带来全局最优？大多数情况下确实不能。但有些问题的结构恰好允许这种"短视"的策略。
买卖股票：你从周一走到周五，看着每天的股价。你要选一天买入、之后某天卖出，赚最多的差价。
关键洞察：最优买入点一定在最优卖出点之前。所以你不需要预知未来——你只需要走过每一天时记住两件事：1）到目前为止最便宜是哪天？2）如果今天卖，利润是多少？走到某天时，你天然知道"过去的最低价"，用今天的价格减去它就是"如果今天卖出的最大利润"。所有天的这个值取最大，就是答案。
贪心之所以有效，是因为这个问题的结构恰好允许"只看过去"就做出最优决策——你不需要回头改变买入时机，因为过去的最低价永远是最佳买入点。
跳跃游戏：你站在一排石头上，每块石头上写着你最远能跳几步。你能不能跳到最后？你不需要规划具体的跳法，只需要维护一个"目前能到达的最远位置"。每走到一块石头，就更新这个最远距离。如果最远距离 ≥ 终点，一定能到达——至于具体怎么跳，不重要。
# 核心思想
贪心 vs 动态规划：
- 贪心：每步取局部最优，不回头。简单但不总是对的
- 动态规划：考虑所有可能，保证全局最优。更通用但更复杂
贪心能用的前提：局部最优选择能导致全局最优（需要证明或直觉判断）
2
3
4
5
# 注意
贪心算法最难的不是写代码，而是证明贪心策略是正确的。如果你不确定贪心行不行，先试动态规划——它一定能给出正确答案。
# 14. 动态规划 — 聪明人的备忘录
# 题目
| # | 题目 |
|---|---|
| 70 | 爬楼梯 |
| 118 | 杨辉三角 |
| 198 | 打家劫舍 |
| 279 | 完全平方数 |
| 322 | 零钱兑换 |
| 139 | 单词拆分 |
| 300 | 最长递增子序列 |
| 152 | 乘积最大子数组 |
| 416 | 分割等和子集 |
| 32 | 最长有效括号 |
# 故事
# 爬楼梯：从电话打爆到门上贴纸条
你要爬一个10级台阶的楼梯，每次可以走1级或2级。有多少种走法？
最直觉的想法是：站在第10级，你是从第9级跨1步上来的，或者从第8级跨2步上来的。所以"到第10级的走法"="到第9级的走法"+"到第8级的走法"。
这看起来很简洁，但执行起来是场灾难。
想象楼梯的每一级上都站着一个人。你站在第10级，打电话问第9级的朋友和第8级的朋友："你那儿有几种走法？"第9级的朋友不知道，于是他又打电话问第8级和第7级。第8级的朋友也不知道，又分别打电话问第7级和第6级……
注意到问题了吗？第8级的朋友接到了两个电话——一个来自你，一个来自第9级。他把同样的问题回答了两遍。第7级的朋友更惨，接了三个电话。越往下，电话越多。到最底下，第1级和第2级的朋友被打爆了——他们要接上百个电话，每次都重复回答同一个问题。
这就是暴力递归的"爆炸"——明明只有10级台阶，电话却打了上百个。
现在换个做法。如果每个人接完第一个电话后，把答案写在一张纸条上贴在门上呢？ 下次有人问，不用再往下打电话，直接看门上的纸条。
第1级贴了"1种"，第2级贴了"2种"。第3级的朋友看看第1级的门和第2级的门：1+2=3种，贴上纸条。第4级看看第2级和第3级的门：2+3=5种……一路贴上去，每个人只需要看两张纸条、写一张纸条。10级台阶，10张纸条就够了。
这就是动态规划——同一个问题只回答一次，答案贴在门上给后面的人看。 从"打爆电话"到"看门上的纸条"，就是从递归到DP的跳跃。
# 打家劫舍：走夜路的小偷
你是一个小偷，一排房子不能偷相邻的两家。每家有不同金额，怎么偷最多？
想象你走在深夜的街道上，一栋一栋地路过。你走到第5栋门前，看了一眼这家的金额，心里在盘算——
你不需要回忆前4栋每一栋的具体决策。你脑子里只需要记住两个数字："算上第4栋的最优战绩"和"不算第4栋的最优战绩"。如果偷这家，上一家就不能偷，所以收益是"不算第4栋的最优"加上这家的金额；如果不偷这家，收益就是"算上第4栋的最优"。取较大值，继续往前走。
关键洞察：你不需要记住所有走过的路，只需要记住走到这儿时的最优状态。过去的所有复杂决策，被压缩成了一个数字。这就是DP的精髓——状态压缩了历史，让你只关注当下。
# 零钱兑换：从1块钱开始凑
你要凑出11块钱，手里有1元、5元、7元三种硬币，最少用几个？
别直接想11块怎么凑——先想简单的。凑1块最少几个？1个（用1元）。凑2块？2个（两个1元）。凑3块？3个。凑4块？4个。凑5块？可以用5个1元，也可以用1个5元——1个更少，所以凑5块最少1个。
到这里你发现了规律：凑任意金额时，你不需要从头试所有组合。你只需要想：最后一个硬币用什么？如果用1元，剩下的金额是"当前-1"，那个金额你已经算过了；如果用5元，剩下的金额是"当前-5"，也算过了；如果用7元，同理。三种选择里，哪个"剩余金额的最少硬币数"最小，就选哪个，再加1（加上最后这个硬币）。
从已知推未知，每一步都站在之前的肩膀上——到11的时候，答案自然浮出水面。
# 核心思想
动态规划三步走：
1. 定义状态：dp[i] 代表什么？（子问题是什么？）
2. 状态转移方程：dp[i] 怎么从之前的状态推出来？
3. 初始条件：最小的子问题答案是什么？
2
3
4
# 常见模式
| 类型 | 例子 | 状态定义 |
|---|---|---|
| 线性 DP | 爬楼梯、打家劫舍 | dp[i] = 到第i个位置的最优解 |
| 背包问题 | 零钱兑换、分割等和子集 | dp[i] = 凑出金额i的最少硬币数 |
| 子序列 | 最长递增子序列 | dp[i] = 以第i个元素结尾的最长子序列长度 |
# 15. 多维动态规划 — 棋盘上的决策
# 题目
| # | 题目 |
|---|---|
| 62 | 不同路径 |
| 64 | 最小路径和 |
| 5 | 最长回文子串 |
| 1143 | 最长公共子序列 |
| 72 | 编辑距离 |
# 故事
一维DP中，每个台阶只需要看前面的台阶。但有些问题天然是二维的——两个维度交织在一起，需要一张表格来记录状态。
# 不同路径：每个格子只问一个问题
你站在棋盘的左上角，只能向右或向下走，要到达右下角。有多少条不同的路？
如果列举所有路径，路径数会随着棋盘变大而爆炸。但你不需要列举——每个格子只需要问自己一个问题："有几条路能到达我？"
答案很简单：你只能从上面或左边来，所以到达你的路 = 到达上面格子的路 + 到达左边格子的路。
第一行的每个格子只能从左边一路走过来——只有1条路。第一列的每个格子只能从上面一路走下来——也只有1条路。这些是"显而易见的答案"，是整张表格的起点。
从这些边界开始，一行一行往下填。每个格子看一眼上面、看一眼左边，两个数加起来，写上自己的答案。到右下角时，答案就水到渠成地出来了。
这就是二维DP的美感：不是穷举所有路径，而是让每个格子自己算清楚"有几条路能到我这儿"。整张表格是一张协作网络，每个格子都站在上面和左边的肩膀上。
# 最长公共子序列：两本书里找共同标注
你和朋友各读了一本书，各自做了一些标注。你想找出你们最长的共同标注序列——不要求连续，但要求顺序一致。
你指着你书里的第 i 个标注，朋友指着他书里的第 j 个标注。如果两个标注一样——太好了，这个标注是公共的，你们各往前翻一个，公共序列长度加1。
如果不一样呢？有两种选择：你跳过你的这个标注（也许你后面有更好的匹配），或者朋友跳过他的。你不知道哪个选择更好——但没关系，两条路都试，取更长的那个。而"跳过之后的最优结果"，你之前已经在表格里算过了。
这就是为什么需要二维表格：一个维度是"你的书翻到第几个标注"，另一个维度是"朋友的书翻到第几个标注"。每个格子记录着"在这个进度下，最长公共序列有多长"。
# 编辑距离：一张代价地图
把单词 "horse" 变成 "ros"，最少需要几步？（可以增、删、改一个字母）
想象一张二维表格，行是 "horse"，列是 "ros"。你站在格子 (i,j) 上，它的含义是"把 horse 的前 i 个字母变成 ros 的前 j 个字母，最少要几步"。
你是怎么到达 (i,j) 的？有三条路：
- 从左上角斜着来 (i-1,j-1)：前面的字母已经处理好了，现在看第 i 个和第 j 个字母——如果一样，免费通过；不一样，花一步替换
- 从上面下来 (i-1,j)：前 i-1 个字母已经变成了前 j 个字母，那第 i 个字母是多余的，花一步删掉它
- 从左边过来 (i,j-1)：前 i 个字母已经变成了前 j-1 个字母，还差第 j 个字母，花一步插入它
三条路，选代价最小的那条。整张表格就像一张代价地图，从左上角 (0,0) 走到右下角——每个格子都记着"走到这里最少花几步"，右下角就是最终答案。
# 核心思想
一维 DP 不够用时，就加一个维度！
- 两个字符串的问题 → dp[i][j] 表示"第一个串前i个 vs 第二个串前j个"
- 网格问题 → dp[i][j] 表示"从起点到(i,j)的最优解"
- 区间问题 → dp[i][j] 表示"从i到j这个区间的最优解"
2
3
4
# 16. 技巧 — 数学魔术
# 题目
| # | 题目 |
|---|---|
| 136 | 只出现一次的数字 |
| 169 | 多数元素 |
| 75 | 颜色分类 |
| 31 | 下一个排列 |
| 287 | 寻找重复数 |
# 故事
只出现一次的数字：一群人排队，除了一个人外其他人都有一个双胞胎。怎么找出那个落单的人？
魔术般的解法：让所有人报数，全部异或（XOR）起来。因为 a XOR a = 0，双胞胎互相抵消，最后剩下的就是落单的那个！
多数元素（摩尔投票法）：找出数组中出现次数超过一半的元素。想象一个战场，不同元素代表不同阵营的士兵。每次让两个不同阵营的士兵同归于尽。因为多数元素超过一半，最后活下来的一定是多数阵营。
候选人 = 第一个元素，票数 = 1
遇到相同的 → 票数+1
遇到不同的 → 票数-1
票数归零 → 换候选人
2
3
4
颜色分类（荷兰国旗问题）：把红白蓝三种颜色排好序。用三个指针：low 管红色区域的边界，high 管蓝色区域的边界，mid 从左到右扫描——遇到红色换到前面，遇到蓝色换到后面，白色跳过。
# 核心思想
这类题通常有巧妙的数学性质或位运算技巧：
- XOR：自身异或为0，用于找"唯一"的元素
- 摩尔投票：用"抵消"思想找多数元素
- 三指针分区：荷兰国旗问题的经典解法
- 数学规律：找规律、找周期
2
3
4
5
# 17. 快速解题的 7 个元思维
小故事帮你理解"这个算法是什么"，但拿到一道新题时，你面对的第一个问题是：我该用什么算法？ 以下 7 个元思维，是从"读懂题"到"写出代码"之间那段最关键的思考过程。
# 元思维 1：从数据规模倒推算法
这是最实用的技巧。看一眼数据范围，就能排除大部分不可能的解法。
n ≤ 20 → 暴力搜索 / 回溯 / 状态压缩 DP O(2^n) 或 O(n!)
n ≤ 100 → O(n^3) 三重循环、Floyd
n ≤ 1,000 → O(n^2) 双重循环、二维 DP
n ≤ 100,000 → O(n log n) 排序、二分、堆、分治
n ≤ 1,000,000 → O(n) 双指针、滑动窗口、哈希表、单调栈
n > 10^7 → O(log n) 或 O(1) 纯数学 / 二分
2
3
4
5
6
例子：题目给了 n ≤ 10^5 的数组，让你求什么最优解——O(n^2) 的暴力肯定超时，你应该往 O(n log n) 或 O(n) 的方向想。这一步就把搜索空间缩小了一大半。
# 元思维 2：暴力优先，再想优化
很多人一上来就想最优解，想不出就卡住了。正确的做法是：
第1步：写出暴力解（哪怕 O(n^3)）
第2步：找到暴力解中的"浪费"——重复计算？多余遍历？
第3步：用合适的数据结构/算法消除浪费
2
3
| 暴力中的浪费 | 优化手段 |
|---|---|
| 反复查找某个值存不存在 | → 哈希表 |
| 两层循环遍历所有配对 | → 排序 + 双指针 |
| 重复计算子问题 | → 动态规划（记忆化） |
| 每次都重新算区间和 | → 前缀和 |
| 每个元素都和所有其他元素比较 | → 单调栈 / 堆 |
"先有暴力，再有优化"比"直接想最优解"靠谱得多。
# 元思维 3：识别问题模式（Pattern Matching）
80% 的题都可以归入几个固定模式。当你读完题，问自己这几个问题：
"求连续子数组/子串的最值" → 滑动窗口 or 前缀和
"求所有可能的组合/排列/子集" → 回溯
"求最优解且有重叠子问题" → 动态规划
"在有序数据中查找" → 二分查找
"求最短路径/最少步数" → BFS
"求连通性/探索所有路径" → DFS
"下一个更大/更小元素" → 单调栈
"频繁取最大/最小值" → 堆
"判断是否存在/去重/计数" → 哈希表
"两个有序序列的合并/交集" → 双指针
2
3
4
5
6
7
8
9
10
训练方法：每做完一道题，写一句话总结它属于哪个模式。做 30 道后你的模式识别能力就会质变。
# 元思维 4：问题转化 — 把陌生变熟悉
高手和新手最大的差距不是知道更多算法，而是能把陌生问题转化成熟悉问题。
经典转化思路：
| 原问题 | 转化为 |
|---|---|
| "能否分割成两个等和子集" | 0-1 背包：能否凑出 sum/2 |
| "课程表能否修完" | 有向图是否有环（拓扑排序） |
| "最长回文子串" | 区间 DP 或 中心扩展 |
| "寻找重复数（不能改数组）" | 链表找环（快慢指针） |
| "接雨水" | 每个位置能接的水 = min(左边最高, 右边最高) - 自身高度 |
遇到新题时问自己："这个问题本质上和我见过的哪个问题类似？"
# 元思维 5：状态定义 — 动态规划的灵魂
DP 难不在写转移方程，而在定义状态。状态定义对了，方程自然出来。
定义状态的技巧：
1. 问自己：为了求出最终答案，我需要记住什么信息？
2. 这些信息就是 dp 的维度
例：打家劫舍
- 我需要知道"考虑前 i 家时的最大收益" → dp[i]
例：编辑距离
- 我需要知道"word1 前 i 个字符变成 word2 前 j 个字符的代价" → dp[i][j]
例：买卖股票（带冷冻期）
- 我需要知道"第 i 天结束后，我是持有/不持有/冷冻状态" → dp[i][state]
2
3
4
5
6
7
8
9
10
11
一个好的状态定义满足两个条件：
- 无后效性：未来的选择只取决于当前状态，不取决于怎么到达这个状态
- 能推导：当前状态可以从之前的状态推导出来
# 元思维 6：不变量思维 — 在变化中找到不变的锚
很多巧妙解法的核心是维护一个不变量（invariant）——在整个过程中始终为真的性质。
二分查找的不变量：
"答案一定在 [left, right] 之间"
→ 每次循环缩小范围但保持这个不变量
快慢指针找环的不变量：
"如果有环，快指针终将追上慢指针"
→ 利用速度差必然在环内相遇
滑动窗口的不变量：
"窗口内始终满足/不满足某个条件"
→ 移动左右边界来维持这个性质
单调栈的不变量：
"栈内元素从底到顶单调递减/递增"
→ 每次入栈时弹出违反单调性的元素
2
3
4
5
6
7
8
9
10
11
12
13
14
15
当你不知道怎么优化时，试着找一个不变量。它就是算法正确性的"锚"。
# 元思维 7：边界条件 — 80% 的 bug 藏在这里
算法想对了，但代码就是不过？大概率是边界问题。
必须检查的边界清单：
□ 空输入（数组为空、字符串为空、树为 null）
□ 只有一个元素
□ 只有两个元素
□ 全部相同
□ 已经有序 / 完全逆序
□ 最大值和最小值（溢出？）
□ 二分查找的 left/right 更新是否会死循环？
□ 链表操作是否处理了头节点和尾节点？
□ 递归的终止条件是否正确？
□ DP 的初始状态是否正确？
2
3
4
5
6
7
8
9
10
11
建议：写完代码后，用最小用例（空、1个元素、2个元素）在脑中走一遍。这30秒能省你30分钟的 debug。
# 总结：解题的完整思考链
拿到题目
│
▼
① 读题 → 提取关键词（连续？有序？所有可能？最优？）
│
▼
② 看数据规模 → 排除不可能的复杂度
│
▼
③ 模式识别 → 这像哪类问题？
│
▼
④ 先想暴力 → 能不能直接穷举？
│
▼
⑤ 找浪费 → 暴力解里哪里重复了？
│
▼
⑥ 选择数据结构/算法 → 消除浪费
│
▼
⑦ 定义状态（如果是 DP）→ 写转移方程
│
▼
⑧ 写代码 → 注意边界条件
│
▼
⑨ 用最小用例验证 → 提交
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
记住：算法能力 = 模式识别 × 问题转化 × 边界处理。三者缺一不可。
# 学习路线总结
第一阶段（打基础，建立信心）
哈希表 → 双指针 → 滑动窗口 → 普通数组/矩阵
第二阶段（掌握核心数据结构）
链表 → 栈 → 堆 → 二叉树
第三阶段（攻克算法难关）
二分查找 → 回溯 → BFS/DFS → 贪心
第四阶段（最终boss）
动态规划 → 多维动态规划
彩蛋关
技巧题
2
3
4
5
6
7
8
9
10
11
12
13
14
每个模块的学习方法：
- 先读这份指南里的故事和核心思想
- 从该模块最简单的题开始做（如哈希表先做"两数之和"）
- 做不出来看题解时，重点理解"为什么这么想"，而不是记代码
- 做完一道题后回顾，确认它用了哪个模式
- 再做下一道，逐步提升难度
祝你刷题愉快！🎯