从暴力解到最优解：408 算法大题专题（总纲）

Intro

打开任何一本 408 复习资料，算法设计题给出的几乎都是最优解：双指针、三次逆置、摩尔投票……这些解法确实漂亮，但它们有一个共同的问题——你在考场上第一时间想到的，往往是另一个解。

那个解通常长这样：双重循环、开个辅助数组、把链表结点全存下来再摆一遍。它朴素、直接、一眼能看懂，我们习惯叫它「暴力解」。

这个专题将带着你：把 408 历年算法设计真题的暴力解和最优解放在一起讲。每道题都从暴力解写起，算清楚它按判分口径值多少分，再找出它浪费在哪里，最后一步步改造成最优解。

值得先把暴力解写对

判分口径：正确性和最优性是两个维度

408 算法设计题的题面有一个固定句式：「设计一个时间上尽可能高效的算法」。这句话透露了判分的结构——

正确性：你的算法能不能正确解出这道题。思想说得清、代码写得对、复杂度分析和实现一致，这部分分就拿到了。用什么方法拿这部分分，判分并不挑剔。
最优性：你的算法有没有达到「尽可能高效」的期望复杂度。只有这一小部分分和方法优劣挂钩。

正确性占大头。一份写对了的 $O (n^{2})$ 暴力解，拿正确性分、丢最优性分——通常意味着这道 10~15 分的大题，主体分都在手里。反过来，一份从资料上背来、但细节写错了的「最优解」，正确性维度直接受损，丢的分远比暴力解多。

**写对的暴力解，稳稳胜过写错的最优解。**这是判分制度决定的，也是这个专题成立的根基。

考试本身就是验证标准

学算法最难的问题是「我怎么知道自己学会了」。408 真题提供了一个现成的验证闭环：

拿到题，先写暴力解——检验你有没有真正理解题意；
对照判分口径估分——检验这个解在考场上值多少；
找出暴力解的浪费、升级成最优解——检验你是否掌握了那个「优化动作」；
在 OJ 上把两版代码都提交跑通——机器裁判说了算。

每一步都有明确的对错反馈，这比「把标准答案看懂了」可靠得多。

一个统一的视角：算法是更聪明的暴力

把 21 道真题的暴力解和最优解并排放着看，会看到一个规律：

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

所以从暴力解到最优解的路径是固定的三步：

「找浪费」有三个固定的提问：

有没有重复扫描？——同一段数据被扫了很多遍，每遍只带走一点信息。对策：一遍扫描时多记一点（双指针、计数、后缀最值）。
有没有重算已知的东西？——上一轮算过的结果，这一轮从头再算。对策：把中间结果存下来（标记数组、哈希、前缀和）。
有没有放着性质不用？——题目给了有序、给了 BST、给了值域范围，暴力解却当普通数据处理。对策：让性质替你干活（二分、中序、值当下标）。

注意第四种情况：**问完三个问题都答「没有」，那暴力解本身就是这道题的满分解。**历年真题里有相当一部分题属于这种情况——识别出「这题用不着优化」，和会优化同样重要，它能防止你在考场上为不存在的分数去冒险写复杂代码。

2009–2026：21 道算法设计真题全景

从 846 道真题里筛出所有需要动手写算法的设计题，共 21 道。按「题面是否明确要求尽可能高效」分成两组：

第一组：题面要求「尽可能高效」的 12 道

这一组暴力解和最优解有真实分差，是专题的主战场。

年份·题号	考什么	起步的暴力解	升级后的最优解
2009·42	单链表倒数第 k 个结点	先扫一遍数长度 L，再走 L−k 步	双指针相距 k 同步走，一遍扫描
2010·42	数组循环左移 p 位	每次挪 1 位、挪 p 轮，或开辅助数组整体搬	三次逆置， $O (n)$ 时间 $O (1)$ 空间
2011·42	两个等长升序序列的中位数	归并着数到第 n 个	二分，每轮同时砍掉两边一半
2012·42	两链表共同后缀起点	枚举每个起点逐一比对	先走掉长度差，再同步前进
2013·41	主元素	双重循环给每个数计数	摩尔投票：候选抵消 + 一遍验证
2015·41	链表按绝对值去重	每个结点向后扫删重复， $O (n^{2})$	值域标记数组，空间换时间 $O (n)$
2016·43	集合划分（个数差最小、和差最大）	全排序再对半分	类快排 partition 找第 ⌊n/2⌋ 小
2018·41	未出现的最小正整数	从 1 开始逐个候选回数组里找	标记数组，两遍线性扫描
2019·41	链表重排 (a₁,aₙ,a₂,aₙ₋₁,…)	结点存进数组按序重连	找中点 + 逆置 + 交叉合并， $O (1)$ 空间
2020·41	三个升序数组的三元组最小距离	三重循环枚举， $O (n^{3})$	三指针，每轮推进最小者， $O (n)$
2022·41	判定顺序存储的二叉树是否 BST	中序输出到数组，再判有序	中序遍历时与前驱直接比较
2025·41	res[i] = A[i] 与其后缀最大值的乘积	每个 i 向后扫一遍求最大， $O (n^{2})$	反向一遍扫描，顺手维护后缀最大

第二组：直观写法就是满分解的 9 道

这一组题面没有高效硬约束，朴素解法和标准答案基本重合——重点变成「识别出不用优化，把细节写对」。

年份·题号	考什么	说明
2014·41	二叉树 WPL	一遍遍历带着深度累加，直观写法即标答
2017·41	表达式树转中缀表达式	中序遍历 + 加括号，难点在括号取舍细节
2019·42	用循环单链表实现队列	数据结构设计题，考的是设计取舍
2020·42	前缀编码译码	数据结构设计题（二叉树）
2021·41	EL 路（欧拉路径）判定	邻接矩阵逐行数度数；读入矩阵本身就要 $O (n^{2})$ ，这就是下限
2022·42	10 万个数里找最小的 10 个	容量为 10 的大根堆一遍扫描；全排序思路对但杀鸡用牛刀
2023·41	有向图 K 顶点	逐顶点数出度入度，矩阵存储下 $O (n^{2})$ 即最优
2024·41	拓扑排序唯一性判定	拓扑排序过程中检查每步候选数
2026·41	BST 最近邻	全树遍历求最小差已是正确解；利用 BST 有序性可再剪枝

每道题的具体判分细节以题库解析为准，专题会按上面第一组逐题展开成文。

考场策略：把这个专题变成分数

**先写暴力，确认正确，再谈优化。**设计思想那一问，先把朴素思路完整说清；有把握再升级。半途而废的优化，两头的分都拿不到。
**时间不够时，交一份写对的暴力解。**它拿走正确性维度的主体分。复杂度分析那一问照实写 $O (n^{2})$ ——复杂度分析和实际算法一致本身就是得分点，谎报成 $O (n)$ 反而在正确性上出问题。
**看到题面写「尽可能高效」，心里预留升级步骤。**这四个字出现时，最优性分才存在；没出现时，别给自己加戏。
**优化动作是可枚举的。**上面 12 道题用到的手段一共就几类：双指针、标记数组/空间换时间、二分、原地逆置、一遍扫描带状态、利用结构性质。每学会一类，就多一片能升级的题。

专题目录

第一组 12 篇已全部更新，按优化手段归类（同一手段的题放在一起，练完一类就能迁移到同组其他题）：

空间换时间（值当下标）

双指针 / 多指针消掉重复扫描

利用有序性（二分）

2011·42 两个升序序列的中位数：从归并计数到双数组折半

原地逆置

一遍扫描 + 数学性质 / 结构性质

partition 单侧递归

2016·43 集合划分：从全排序到 partition 找第 k 小

第二组：识别「不用优化」

第一组教的是「怎么优化」；第二组教的是**「怎么判断一道题到底要不要优化」——这两件事合起来才是完整的判断力。考场上很多失分源于对着不用优化的题瞎优化**：看到图就想遍历、看到树就想递归建结构、明明题目没要求还去把复杂度往下压，结果把简单题写复杂、把细节写错。

判断一道题要不要优化，就问两个问题：

题面有没有「尽可能高效 / 比较次数尽可能少」这类字样？ 没有，多半就是「写对即可」；有，才需要预留优化步骤。
直观写法的复杂度，是不是已经等于读入规模？ 邻接矩阵读一遍就是 $O (n^{2})$ 、遍历每个结点就是 $O (n)$ ——碰到这个下界，就没有优化空间了，直观写法即最优。

按这两问，第二组分成两半：

直观写法即满分（读入/遍历规模就是下界，或本身是设计题）

警示：看着像不用优化，其实暗藏优化要求（这两道是通向第一组的桥）

从暴力解到最优解：408 算法大题专题（总纲） ​

Intro ​

值得先把暴力解写对 ​

判分口径：正确性和最优性是两个维度 ​

考试本身就是验证标准 ​

一个统一的视角：算法是更聪明的暴力 ​

2009–2026：21 道算法设计真题全景 ​

第一组：题面要求「尽可能高效」的 12 道 ​

第二组：直观写法就是满分解的 9 道 ​

考场策略：把这个专题变成分数 ​

专题目录 ​

第二组：识别「不用优化」 ​