算法是更聪明的暴力

场景引入

面试进行到第 15 分钟，题目读完了，你能说出十几个算法的名字，却说不出这道题该用哪一个。脑子里过了一遍双指针、哈希、动态规划，每一个都像又都不像。于是你开始沉默，面试官开始记笔记。

这种卡壳很少是因为学得少。多半是因为，学过的东西是按名字存放的——「滑动窗口是什么」「回溯的模板长什么样」——而考场上需要的是按动作取用：拿到一道陌生的题，第一步做什么，第二步做什么。

这篇是全站的纲领，讲的就是那套动作。它只有三步，而且对本站后面每一章都适用。

所有算法共用同一批原子操作

把任意一道题的暴力解和最优解并排放着看，会看到一个规律。

算法的原子操作只有四种——增、删、改、查。暴力解用最直接的方式组织这些操作；递归换了一种组织顺序；回溯是带撤销的穷举；动态规划是记住了中间结果的穷举。最优解并没有发明新的原子操作，它只是砍掉了暴力解里重复和无用的那部分。

这句话的实际用处在于，它把「想出最优解」这件靠灵感的事，换成了一件可以按部就班做的事：先把暴力解写出来，再去它身上找浪费。

暴力解在这里有双重身份。它是最终答案的草稿，也是理解题意的验收标准——写不出暴力解，通常说明题目还没读懂，这时候去想最优解是空想。

找浪费的三个提问

「找到浪费」听起来仍然含糊。把它拆成三个固定的提问，就变得可以操作了。拿到暴力解之后，依次问一遍。

一、有没有重复扫描？

同一段数据被扫了很多遍，而每一遍只带走一点点信息。

举个例子：给定一个数组，求每个元素右边第一个比它大的数。暴力解是对每个位置向右扫到底，时间 O(n²)。浪费在哪？位置 i 向右扫的时候，其实把 i+1、i+2 的右边也顺路看了一遍，但看完就扔了，轮到 i+1 时再从头看一次。

对策是一遍扫描时多记一点。把「还没找到答案的位置」暂存在一个栈里，新元素进来时把栈里比它小的都弹出并结算——这就是单调栈，时间降到 O(n)。

同一个提问也能推出滑动窗口（子串问题里反复重新统计窗口内的字符）、前缀和（反复重新累加同一段区间）、后缀最值（反复重新求右侧最大值）。

二、有没有重算已知的东西？

上一轮已经算出来的结果，这一轮从头再算一遍。

最直白的例子是递归求斐波那契。fib(5) 会展开出两棵子树，其中 fib(3) 被完整算了两次，fib(2) 被算了三次。递归树越深，重复得越离谱。

// 暴力递归：fib(n) 的调用次数随 n 指数增长
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

对策是把中间结果存下来。加一个备忘录，每个子问题只算一次，指数级直接降到线性。这个动作再往前一步，把递归改写成自底向上的递推，就是动态规划。

标记数组、哈希表记录已访问节点、图遍历里的 visited，都属于这一类。

三、有没有放着性质不用？

题目明明给了一个额外条件，暴力解却把数据当成一堆无序的东西处理。

有序数组还在逐个比较，就该想到二分；给的是二叉搜索树却做了完整遍历，就该想到左小右大能让你每层砍掉一半；元素值域只有 0 到 100，还在做基于比较的排序，就该想到把值直接当下标去计数。

这三个提问覆盖的范围很广，但它们的形状是一样的：先指出暴力解在做什么无用功，再找一个结构或一条性质来替你干掉它。

第四种情况：三个都答「没有」

这一条容易被忽略，实际用处很大。

三个提问都答「没有」，说明这道题的暴力解本身就是最优解。反转单链表要动到每一个节点，你不可能比 O(n) 更快；求数组最大值也一样。这时候继续琢磨「怎么优化」是在为不存在的分数冒险。

识别出「这题用不着优化」，和会优化同等重要。它能让你在时间有限的场合把力气放对地方。

先写对暴力解，在三个场合都换得到分

上面这套动作有一个共同前提：先把暴力解写对，再谈优化。这个顺序在三种考法下都成立，只是换来的东西不同。

考研初试的算法设计题，判分分成正确性和最优性两个维度，而正确性占大头。一份写对的 O(n²) 解拿到正确性分，只丢掉最优性那一小部分；一份从资料上背来、细节却写错的「最优解」，正确性维度直接受损，丢的分反而更多。这一段的详细拆解在考研版的 408 专题里。

复试机试按通过的测试点计分。数据规模小的测试点，暴力解照样能过，能捞回一部分分。写不出最优解时交一份能跑的暴力解，好过交一份空白。

求职面试里，这套动作本身就是面试官想看的对话流程：你先讲暴力解并说清它为什么正确，面试官问「能不能更快」，你答出是哪一种浪费，然后给出优化。全程沉默着憋最优解，即使最后写出来了，你也少展示了一大半东西。

另一条线索：递归的两种思维

前面讲的是横向的动作——从暴力解走到最优解。还有一条纵向的线索，讲的是这些算法彼此之间的血缘关系。

它的起点是二叉树。二叉树上的递归只有两种思维方式：

• 遍历思维：像走路一样把整棵树走一遍，用外部变量记录沿途结果。
• 分解思维：把「整棵树的答案」拆成「左子树的答案」和「右子树的答案」，用返回值组装。

这两种思维不局限在二叉树里：

回溯算法就是遍历思维加上「做选择、撤销选择」；动态规划就是分解思维加上备忘录；BFS 就是层序遍历换了个场景。所以本站把二叉树那一章放得比较重——它是后面几章共同的原型，递归思维：遍历 vs 分解那篇建议早点读。

怎么用这套动作读本站

本站后面每一章讲的都是一个具体技巧，而每个技巧都能在这两条线索上定位：

• 它消除的是哪一种浪费（横轴）
• 它属于哪一种递归思维的延伸（纵轴）

举几个例子：滑动窗口消除的是重复扫描，血缘上属于数组双指针；动态规划消除的是重算已知，血缘上属于分解思维；二分查找是利用有序这条性质，本身不涉及递归思维。

读一篇新文章时，如果能先答出这两个问题，这篇文章在你脑子里就有了位置，不会读完就散。遇到陌生题目时，也能反过来从「我发现的浪费是哪一种」出发，去找对应的工具。

延伸阅读

• 复杂度分析 —— 判断一个解「值不值得优化」的量化工具
• 如何高效刷题：框架思维 —— 这套动作怎么落到日常练习节奏里
• 二叉树的递归思维：遍历 vs 分解 —— 纵向线索的起点
• 考研 408 版：从暴力解到最优解 —— 同一套动作在 21 道真题上的逐题演练，含判分口径拆解