你大概见过那张流传很广的图:“DSA 很难,直到我学会了这 15 种模式”——双指针、滑动窗口、二分搜索、频率计数、单调栈、前缀和、贪心、回溯、DFS、BFS、动态规划……图做得很好,但它有一个危险的暗示:算法 = 背 15 个模板。照这个思路学,你会陷入”这题是滑窗还是双指针?”的猜谜游戏,题目稍微一变形就懵。这篇反过来讲:这 15 种模式不是 15 个独立的招式,它们是同一个思想的 15 张面孔。 把那个思想想通,15 个模式会自己在你脑子里各就各位。
一句话主线
所有算法题都是”在一堆候选答案里找目标”。暴力解法 = 把候选全部看一遍。每一种算法模式,本质上只是一种”敢不看某些候选”或”不把同一个候选看两遍”的理由。理由只有三类:跳过(证明某些候选不可能是答案)、记住(算过的结果存起来别重算)、按秩序走(实在没捷径时,保证每个候选恰好看一次)。
下面先把”候选答案”这个母体讲清楚,再带着三个动词,把 15 种模式一个一个放回它们该在的位置。
第零步:先看清母体——一切都是搜索
随便拿一道题:“数组里找两个数,加起来等于 9”。
这道题的候选答案是什么?是”所有可能的数对”。数组有 1000 个数,数对就有大约 50 万个(1000 × 999 ÷ 2)。暴力解法就是把这 50 万对全部检查一遍——两层循环,谁都会写,而且它永远是对的,因为”全看一遍”不可能漏。
所以暴力不丢人,它是所有算法的出发点和正确性的底线。问题只有一个:慢。数组变成 100 万个数,数对就是 5000 亿个,检查不完了。
于是所有”算法”要回答的其实是同一个问题:
这 50 万个候选里,哪些是我可以不看的?我凭什么敢不看?
“凭什么敢”这四个字是全文的钥匙。你不能因为懒而跳过一个候选,你必须有证明:被跳过的候选不可能是答案。 每一种算法模式,就是一种现成的证明。而所谓时间复杂度,不过是”证明完之后,你还剩多少候选要看”:暴力 O(n²) 是 50 万个全看;如果每一步都能排除掉一整批,就降到 O(n);如果每一步排除一半,就是 O(log n)。
三个动词先总览一遍,后面逐个展开:
| 动词 | 一句话 | 生效前提(问题得有这种结构) | 覆盖的模式 |
|---|---|---|---|
| 跳过 | 证明某些候选不可能,直接排除 | 数据有单调性/有序性(没有就花钱排序买一个) | 双指针、二分、滑动窗口、单调栈、贪心、重叠区间 |
| 记住 | 算过的结果存下来,下次查表 | 计算之间有重复(重叠的子问题) | 频率计数、前缀和、Top-K 堆、动态规划 |
| 按秩序走 | 没有捷径时,保证不重、不漏、每个恰好一次 | 候选有限,且能被系统地编号/生成 | 二叉树遍历、DFS、BFS、回溯、矩阵遍历 |
注意最中间那列:动词不是想用就能用的,问题必须先有对应的结构。 这正是”看到题就套模板”会翻车的原因——模板对了,结构没确认,答案就是错的。下面每个模式,我都按同一个格式讲:它面对什么形状的问题、暴力怎么做、它凭什么敢跳过/复用、一个具体的小例子。
家族一:跳过——排除法的五种姿势
这一族的共同前提是单调性:数据里存在某种”朝一个方向只增不减(或只减不增)“的秩序。单调性之所以值钱,是因为它让你能从一次比较里读出一批候选的命运。
1. 双指针:一次比较,排除一整行
问题形状:在有序数组里找满足条件的一对数。比如 [1, 3, 5, 7, 9, 11] 里找两数之和等于 14。
暴力是检查所有 15 个数对。双指针的做法:左指针 L 指最小的 1,右指针 R 指最大的 11,算一下 1 + 11 = 12,比 14 小。
关键一步来了——既然最小的数配上最大的数都不够 14,那最小的数 1 配上任何数都不够。 于是”1 和别人组成的所有数对”(共 5 对)被一句话全部排除,L 右移。接着 3 + 11 = 14,找到了。
看清楚这里发生了什么:一次比较,排除了一整批候选。这个推理完全依赖数组有序——如果数组是乱的,“1 + 最大的都不够”推不出任何东西,因为你不知道谁是最大的。每次移动指针排除一批,n 个数最多移动 n 次,O(n²) 的候选空间被 O(n) 步走完。
2. 二分搜索:一次比较,排除一半
问题形状:在有序数据里定位一个目标。[1, 3, 5, 7, 9, 11, 13] 里找 7。
看中间的数,是 7,一次就中——运气好。假设找 11:中间是 7,比 11 小,由于数组有序,7 左边的所有数都比 7 更小,更不可能是 11,左半边整体排除。剩下的一半再看中间……每次砍一半,1000 个数只需约 10 次,10 亿个数只需约 30 次。
它和双指针是亲兄弟:都靠有序性,双指针每次排除”一行”,二分每次排除”一半”。二分的适用面其实比”有序数组找数”宽得多——任何”答案左边全是 No、右边全是 Yes”的判定问题(比如”最小需要多少速度才能按时吃完香蕉”)都能二分,因为那条 No/Yes 的分界线就是一种单调性。
3. 滑动窗口:别把窗户拆了重装
问题形状:在数组/字符串里找满足条件的连续区间。比如”长度为 3 的窗口,和最大是多少”:[2, 1, 5, 1, 3, 2]。
暴力:每个起点都从头加 3 个数,大量数字被反复加。滑窗的观察:窗口从 [2,1,5] 挪到 [1,5,1],中间的 1, 5 根本没变——新窗口 = 旧窗口 − 出去的 2 + 进来的 1,一次减一次加,O(1) 完成更新。
严格说滑窗是”跳过”和”记住”的混血:它记住了上一个窗口的结果(复用),从而跳过了窗口内部的重算。可变长度的滑窗(比如”最长无重复字符子串”)多一层排除逻辑:窗口一旦非法(出现重复),左边界只能右移、永不回头——因为左边界回头只会让窗口更大、更不可能合法,这又是一条单调性。
4. 单调栈:被压住的矮个子,永远没戏
问题形状:给数组里每个元素找”右边第一个比它大的数”。[1, 3, 2, 4]。
暴力:每个元素向右扫,O(n²)。单调栈的观察:从左往右走,遇到 4 的时候,前面还没找到答案的 3 和 2,答案都是 4。那 1 呢?1 早在 3 出现时就有答案了。
做法是维护一个”还在等答案的候选”栈,并保持栈内从底到顶递减。新元素进来,把栈顶所有比它小的都弹出——弹出的那一刻,它们的答案就是这个新元素。凭什么弹出后不用再管?因为一个数如果比新元素小、又排在新元素前面,那后面任何元素若要”第一个大于它”,必然先撞上这个更近更大的新元素——它作为别人答案的资格已经被永久剥夺了。每个元素最多进栈一次、出栈一次,O(n)。
单调栈是这族里最不直觉的一个,但它的排除逻辑最典型:不是排除”不可能是答案的候选”,而是排除”不再需要保留的状态”。
5. 贪心:选完就不回头,是最激进的排除
问题形状:一步一步做选择,求全局最优。比如凑金额 38,面额有 25、10、5、1(那张图里的例子):每次选”能放下的最大面额”——25,剩 13;10,剩 3;1、1、1。完成。
贪心每一步只做一个选择,并且永不反悔——这等于把”如果当初选别的会怎样”的所有分支全部排除,搜索树被砍成一条线,所以它快得惊人。
但贪心是三族里最需要证明的:它成立,当且仅当你能论证”局部最优的选择,不会堵死全局最优”(教科书叫贪心选择性质)。上面这套面额恰好满足;换成面额 [1, 3, 4] 凑 6,贪心给出 4+1+1 三枚,而正确答案是 3+3 两枚——贪心失效,因为选 4 堵死了更优解。这时怎么办?退回到”把各种选择都试试但别重算”——那正是动态规划,后面会讲。记住这条边界:贪心和 DP 是同一道题谱系上的两端,能证明不回头就贪心,不能证明就 DP。
6. 重叠区间:没有秩序,就花钱买一个
问题形状:一堆区间,合并重叠的。[1,4] 和 [3,6] 重叠,合并成 [1,6]。
区间乱序时,任何两个区间都可能重叠,只能两两比较,O(n²)。但先按左端点排序(花费 O(n log n)),就出现一条可以利用的秩序:如果当前区间和上一个合并结果都不重叠,那它后面的区间(左端点更靠右)更不可能与之重叠。 于是排序后只需一次线性扫描,每个区间只和”最近的合并结果”比一次。
这个模式的启示比模式本身重要:单调性不是等来的,是可以制造的。 很多题的第一步”先排序”,本质就是花 O(n log n) 的钱,买一张”跳过”的许可证。
家族二:记住——你唯一的敌人是重复计算
这一族处理另一种浪费:候选没多看,但同一个计算做了很多遍。药方统一:第一次算完存起来,以后查表。空间换时间。
7. 频率计数:数一遍,以后全是查表
问题形状:关于”出现次数”的一切——出现最多的元素、两个词是否互为变位词。比如 [a, b, a, c, b] 里每个字母出现几次。
暴力:对每个字母,扫全表数一遍,O(n²)。频率计数:扫一遍,拿一张哈希表(键值 → 数量)边走边记:a:2, b:2, c:1。之后任何”x 出现几次”都是 O(1) 查表。
它是”记住”最纯的形态:重复劳动(反复数同一个字母)被一张表消灭。哈希表在整个家族二里是头号工具,值得单独记一句:哈希表就是”用 O(n) 空间,把『查找』的价格从 O(n) 打到 O(1)』的批发市场。
8. 前缀和:预付一次,终身查询
问题形状:反复询问”下标 i 到 j 之间的和”。数组 [1, 2, 3, 4]。
每问一次就现加一次,q 次询问就是 O(q·n)。前缀和:预先算一张”从开头加到每个位置”的表 [0, 1, 3, 6, 10],之后任何区间和 = 两次查表相减——(2..4) 的和 = 10 − 1 = 9。预付 O(n),每次查询 O(1)。
它和频率计数是同一个思想的两种存法:一个按”键”记次数,一个按”位置”记累计。共同点是把”询问时的现算”搬到”询问前的预算”,当询问次数多时,这笔预付稳赚。
9. Top-K 元素(堆):只记住擂台上的 K 个人
问题形状:10 亿个数里找最大的 3 个。
全排序要 O(n log n),而且排完 10 亿个只为取 3 个,浪费到荒谬。堆的做法:维护一个只装 3 人的”擂台”(最小堆,堆顶是擂台上最弱的)。新数进来,和堆顶比:比擂台最弱者还弱,直接淘汰——它连前 3 的门槛都够不着,后面更不可能翻身;比堆顶强,踢掉堆顶换它上。每次操作 O(log K),总共 O(n log K)。
你会发现它是个混血儿:“只维护 K 个”是记住(只记住还有资格的),“比堆顶弱直接扔”是跳过(一次比较排除一个候选的全部可能性)。K 远小于 n 时,log K 近乎常数,快得像作弊。
10. 动态规划:把指数级的重复,压成线性的一遍
问题形状:大问题能拆成小问题,而且小问题会被反复用到。经典入门:爬楼梯,每次上 1 或 2 级,上 5 级有几种走法?
自然的想法是递归:走法(5) = 走法(4) + 走法(3)——最后一步要么跨 1 要么跨 2。但直接递归会爆炸:算走法(4) 要用走法(3),算走法(5) 也要用走法(3),走法(3) 被算了两遍;往下走法(2) 被算 3 遍、走法(1) 被算 5 遍……重复量指数增长,n = 50 就算不动了。
可是不同的子问题总共才 5 个。 指数级的时间,花在了反复计算这 5 个问题上。DP 的全部动作就是:每个子问题只算一次,结果记在表里(那张图里的 dp[i][j] 格子就是这张表),要用就查。O(2ⁿ) 塌缩成 O(n)。
很多人觉得 DP 难,其实难的不是”记住”(那只是一张表),而是定义子问题:找到一种拆法,使子问题个数有限、且大问题的答案能由小问题拼出(即图中 dp[i][j] = ↑ + ← 这类转移方程)。一旦子问题定义对了,DP 就退化成”带备忘录的递归”。也请回忆贪心那节的结论:DP 是”不敢贪心时的安全网”——所有选择都考虑,但靠记住而不重算。
家族三:按秩序走——暴力的艺术
有些问题既没有单调性可跳,也没有重复可省——答案可能藏在任何角落,你必须把候选全看一遍。这时算法的全部追求就变成:不重(同一个候选不看两遍)、不漏(一个都不能少)、每个恰好一次。 别小看这件事,乱走的暴力会绕圈、会死循环、会漏,能优雅地”恰好一次”,本身就是本事。
11. 二叉树遍历:递归结构上的固定走法
问题形状:把树上每个节点都访问一遍(求和、找值、打印)。
树是递归定义的(每个节点下面挂着两棵更小的树),所以”走遍它”最自然的方式也是递归:先左子树、再自己、再右子树(中序;调整”自己”的位置就得到前序/后序)。对二叉搜索树,中序遍历会恰好按从小到大的顺序吐出所有节点——那张图里”输出 1 2 3 4 5”就是这个性质。
它看似平凡,却是家族三的地基:后面的 DFS、回溯,骨架都是它。
12. DFS(深度优先):一条路走到黑,靠”记住”防绕圈
问题形状:图或网格的连通性——从 A 出发能到哪些点?岛屿有几个?
策略是”走迷宫”:选一条路一直往深处走,走不动了退一步换条路。图和树有一个致命区别:图里有环,A→B→C→A 会永远绕圈。解法是一张 visited 集合——走过的点记下来,再遇到直接跳过。注意这恰好是动词二”记住”来客串:visited 表就是 DFS 的备忘录,它保证”每个点恰好访问一次”这个承诺成立,n 个点 m 条边,整体 O(n + m)。
13. BFS(广度优先):一圈一圈往外扩,免费赠品是”最短”
问题形状:同样是走遍图,但换个顺序——像水波纹,先访问距离起点 1 步的所有点,再 2 步的,再 3 步的。实现上用一个队列:访问一个点,就把它的邻居排到队尾。
BFS 和 DFS 都能”走遍”,但 BFS 有一件 DFS 给不了的赠品:按层推进意味着第一次碰到目标时,走过的层数就是最短距离——不用比较所有路径,先到就是最短,这是访问顺序本身送的证明。所以记这条边界:只问”能不能到、有几块”→ DFS/BFS 随意;问”最少几步”→ 无脑 BFS。
14. 回溯:会撤销的 DFS,配上”跳过”的剪刀
问题形状:枚举所有组合/排列/棋盘放法——比如 [1,2,3] 的全排列。
候选是一棵”选择树”:第一层选谁打头,第二层选第二个……回溯 = 在这棵选择树上做 DFS,但多一个关键动作:撤销。走到 [1,2,3] 记下答案后,把 3 拿掉、把 2 拿掉,退回 [1] 的状态,再去试 [1,3,…]——图里写的 “explore · backtrack”(探索·回退)就是这两拍。撤销保证了不同分支互不污染,这才能做到”不重不漏”。
回溯还有一把剪刀叫剪枝:发现当前半成品已经不可能合法(比如八皇后中两个皇后已互相攻击),整棵子树直接不进——这是动词一”跳过”来客串。回溯 = 按秩序走(DFS 骨架)+ 记住(路径状态)+ 跳过(剪枝),三个动词的合体,所以它出现在家族三压轴。
15. 矩阵遍历(螺旋):把”走的秩序”本身当成题目
问题形状:按特定路线走完二维网格,比如螺旋序(右→下→左→上,一圈圈向内收)。
它没有任何算法技巧,难点纯粹在秩序的簿记:维护上下左右四条边界,每走完一条边就把对应边界收窄一格。它被放进 15 模式,是因为它把家族三的口号赤裸裸地摆在你面前:所谓遍历,就是设计一个不重不漏的访问顺序,然后严格执行。 写对它的人,才算真的理解”恰好一次”有多需要小心。
合上书,只剩一张决策图
现在把 15 个模式全部忘掉,只留三个问题。拿到新题时按顺序问:
flowchart TD
A[读题:候选答案是什么?<br/>暴力全看一遍要多久?] --> B{数据有单调性/有序性吗?<br/>或者排个序就有?}
B -- 有 --> C[动词一:跳过<br/>找一对数→双指针<br/>找分界线→二分<br/>连续区间→滑动窗口<br/>下一个更大→单调栈<br/>能证明不回头→贪心<br/>区间类→先排序再扫]
B -- 没有 --> D{计算里有重复吗?<br/>同一个东西反复算?}
D -- 有 --> E[动词二:记住<br/>数次数→哈希计数<br/>反复问区间和→前缀和<br/>只要前K个→堆<br/>重叠子问题→DP]
D -- 没有 --> F[动词三:按秩序走<br/>树→递归遍历<br/>图的连通→DFS<br/>最短步数→BFS<br/>枚举所有方案→回溯<br/>网格路线→边界簿记]
C -.贪心证不出来.-> E
F -.走的过程中能剪枝/能记忆.-> C两条虚线值得多看一眼:贪心证明不了就退到 DP;纯遍历走着走着发现能剪枝、能记 visited——三个动词从来不是互斥的,难题往往是动词的组合(回溯 = 三个动词全用上)。
预想一个反对:“讲这么多本质,我刷题时还是得会写模板啊?”——对,模板仍然要练,它是肌肉记忆,让你 5 分钟内写对双指针不出边界 bug。但模板负责手快,本质负责方向:题目一变形(数组变流、一维变二维、求个数变求最值),模板会失灵,而”这题的候选是什么、哪个动词有许可证”永远问得下去。先有方向再练手速,15 个模板才不会变成 15 个互相干扰的咒语。
最后,把整篇压缩成可以带走的三行:
- 暴力永远是起点:先说清候选空间和全看一遍的代价,才谈得上优化——优化就是”少看”或”不重看”。
- 跳过要许可证,记住要有重复,秩序要不重不漏:三个动词各有生效前提,确认结构再动手,而不是看题型猜模板。
- 复杂度 = 你最终看了多少:每步排除一半 → log n;每步排除一批 → n;只是不重算 → 从指数塌回多项式。看懂一个算法,就是看懂它把哪些候选、凭什么理由,划掉了。