Chapter 07
自测与套路判别
前六章逐一建立了复杂度判断与六大套路——这一章不教新东西，而是逼你做最难的事：拿到陌生题面，独立判断该用哪个套路。这才是面试现场真正考的能力。
本章心智模型
- 概念能复述 ≠ 会判别——背得出定义，不等于陌生题面能选对套路。
- 判别靠结构信号（有序？连续子区间？最优子结构？），不是题面措辞。
- 复杂度约束先帮你排除大半套路：先看 n 的规模，再看结构信号。
用法：先合上前面所有章节，纸笔作答，写完再展开答案。直接看答案等于把这章当复习读一遍——没有检索就没有记忆巩固。每一层的题都标了对应章节链接，仅作答错后回查之用，作答时不要先点开。
§套路判别决策树
面试现场拿到题面，判别顺序是固定的：先读约束（n 的规模），再读结构信号。约束砍掉一半分支，结构信号锁定其一。下面这张决策树把这个顺序固化成一条可背诵的脊柱。
§难度梯度金字塔
同一个套路，能复述定义、能讲清原理、能给陌生题面选中它，是三种递进的掌握程度。面试区分人的不是底两层，而是顶层的判别。
§7.1 概念层（对应 01–02）
每题一句话即可作答，考的是定义的精确复述。合上书，逐题写出答案。
§7.2 原理层（对应 03–06）
这一层不问"是什么"，问"为什么成立"。答不出原理，套路就只是背下的模板。
§7.3 应用判别层（综合 01–06）
面试真正考的一层：给一段陌生题面，独立说出用哪个套路、为什么、复杂度是多少。每题作答都要把这三点写全。方括号标注了牵涉的章节。
- 有序数组找两数之和等于 target。选哪个套路？为什么？复杂度？
[牵涉 01 约束 + 03 / 02] - n≤18 的数组，求所有元素和恰为 target 的子集。选哪个套路？为什么？复杂度？
[牵涉 01 + 05] - n=10⁶ 的数组，求第 k 大的元素。选哪个套路？为什么？复杂度？有哪些备选与取舍？
[牵涉 02 堆 + 04] - 无权图中求从起点到终点的最少步数。选哪个套路？为什么 DFS 不行？复杂度？
[牵涉 05] - 求一个数组的最大连续子数组和。选哪个套路？为什么？复杂度？和前缀和、分治相比如何？
[牵涉 03 + 06] - 判断单链表是否有环，若有则找出入环点。选哪个套路？为什么？空间复杂度？
[牵涉 02 + 03]
亲手画一张图
合上教程，在纸上凭记忆画出起点页的概念地图——只画 复杂度、数据结构、四大套路族、套路判别 这几个块和它们的箭头。画完回到 index.html 的图 0 对照：你画的图里，复杂度是在顶端约束其他、还是被你画成了平级的一个套路？这个位置关系正是本教程的核心。
答案（三个层全部做完再展开）
概念层
- 当 n 足够大，常数与低阶项相对最高阶项可忽略；Big-O 描述的是运行时间随 n 增长的趋势量级，不是精确耗时。比较两算法谁更优，比的是量级而非常数。
- n≤10⁶ 时目标为 O(n) 或 O(n log n)；O(n²)（约 10¹² 次操作）必然超时。这是约束反推复杂度的典型一步。
- 数组按下标随机访问 O(1)、任意位置插入 O(n)（要搬移后续元素）；链表随机访问 O(n)（要逐个走）、已知节点处插入 O(1)（只改指针）。差异源于内存布局：数组连续、链表靠指针串联。
- 取堆顶最值 O(1)；弹出最值 O(log n)（弹出后要下沉重建堆序）。
- 序列中每个元素至多入栈一次、出栈一次，总操作量与 n 成正比，故 n 次操作均摊到每步是 O(1)，整体 O(n)。内层 while 弹栈的总次数被"每个元素只出栈一次"封顶。
deque两端入队出队均 O(1)；list在头部pop(0)是 O(n)（要整体前移）。做队列必须用deque。
原理层
- 前提是数组有序：当前两数之和偏大就右指针左移（必变小）、偏小就左指针右移（必变大），每步都能确定排除一侧。无序时移动指针不能保证和的单调变化，排除逻辑不成立。
- 左右指针都只向右移动、各自至多走 n 步，合计移动量 O(n)；窗口扩张与收缩共享这个总预算，故整体线性，而非每个右端点都重扫一遍的 O(n²)。
- 依赖单调性：判定函数对待求量是单调的（如"用 ≤x 的容量能否完成"随 x 单调由否变是），于是可行区间与不可行区间被一个边界分开，二分这个边界即可。
- 唯一本质区别是节点的处理顺序：DFS 用栈（递归即隐式栈）一路走到底再回退，BFS 用队列按距起点的层数由近及远扩展。区别完全由"栈 vs 队列"造成。
- 撤销选择把状态恢复到进入该分支前，使同一份路径数据能被复用去探索下一个兄弟分支。省掉它，前一分支的选择会污染后续分支，枚举出错。
- DP 两前提：最优子结构（大问题的最优解由子问题最优解拼成）与子问题重叠（同一子问题被反复求解，故值得记忆化）。贪心在缺少"局部最优能导向全局最优"这一性质时失效——即必须靠回溯/全局权衡才能得最优解的题，贪心会错。
应用判别层
- 双指针。数组已有序，对撞双指针 O(n) 时间、O(1) 空间；哈希表也能 O(n) 时间但要 O(n) 额外空间。有序这一信号让双指针在省空间上胜出。
- 回溯枚举 + 剪枝。n≤18 这个极小约束就是"枚举所有方案"的信号，子集数 2ⁿ 在此规模可接受。沿决策树 DFS，对每个元素选/不选，配合和超过 target 即剪枝。复杂度 O(2ⁿ) 量级。
- quickselect 或 堆。quickselect 平均 O(n)、最坏 O(n²)；大小为 k 的堆遍历一遍 O(n log k)，适合数据流；全排序 O(n log n) 做了多余的工作，偏慢。第 k 大不需要整体有序，故避免排序。
- BFS。无权图中 BFS 按层扩展，第一次到达终点即最短步数；DFS 先一头扎到底，首次到达不保证是最短路径。复杂度 O(V+E)。
- DP（Kadane）。令 dp[i] 为以 i 结尾的最大子数组和，dp[i]=max(nums[i], dp[i-1]+nums[i])，O(n) 时间、O(1) 空间。前缀和需配合"当前最小前缀"也能 O(n)；分治 O(n log n) 偏慢。Kadane 最简最快。
- 快慢指针（Floyd）。快指针每步 2 格、慢指针 1 格，有环必相遇；相遇后将一指针移回头部、两指针同速前进，再次相遇点即入环点。时间 O(n)、空间 O(1)，胜过用哈希集合记录访问节点的 O(n) 空间解法。