10 综合通关：分治与贪心的选型模式与面试总结

综合通关：分治与贪心的选型模式与面试总结

摘要

本文是整个专栏的压轴综合篇。前九篇分别深入剖析了分治和贪心的各种模式；这一篇的任务是把所有碎片化的知识连成一张网——分治与贪心与 DP 的三角关系是什么？面试中如何快速识别用哪种范式？常见的错误是什么？本文不引入新的 LeetCode 题目，而是从全局视角重新审视已讲的所有内容，给出一套可在面试中立即应用的选型决策框架。

---

第 1 章 三种范式的本质与边界

1.1 动态规划（DP）的本质

DP 解决的是有最优子结构 + 重叠子问题的问题。

• 最优子结构：全局最优解可以由子问题的最优解组合得到
• 重叠子问题：相同的子问题被重复计算，记忆化可以加速

DP 的核心操作是枚举所有可能的”最后一步”，从而建立递推关系。

$\text{DP}(i)=\min /\max \{f(\text{DP}(j),\text{cost}(j,i)):j<i\text{ 且 }j\to i\text{ 合法}\}$

DP 的决策在每一步考虑了所有可能性，通过记忆化避免重复计算。

1.2 贪心的本质

贪心是 DP 的特例：当某个问题的 DP 转移方程中，最优的”最后一步”可以不看其他选项，只根据局部信息直接确定时，DP 退化为贪心。

形式化：若 DP 转移 $\text{DP}(i)=f(\text{DP}(j^{\ast }),...)$ 中，$j^{\ast }$ 可以通过局部比较（如排序、最大/最小）直接确定，而不需要遍历所有 $j$，则有贪心解法。

贪心选择性质：每一步的贪心选择都是安全的，即不会”封死”全局最优的路径。这通常通过交换论证（Proof by Exchange）来证明。

1.3 分治的本质

分治解决的是可以被拆成独立子问题的问题。

• 与 DP 的区别：分治的子问题不重叠（或重叠可以接受，但通常不需要记忆化）
• 与贪心的区别：分治的”最优”是从左右子问题的解合并得到，而贪心是不回头地做选择

分治的三要素：

1. 分：将问题拆成两个（或多个）独立子问题
2. 治：递归解决每个子问题
3. 合：将子问题的解合并为全局解

分治的关键在于合并步骤的设计（如归并排序的合并、最大子数组的跨越中点情形）。

1.4 三者的三角关系

         DP（最通用）
        /           \
  贪心（DP特例）   分治（子问题独立）

比较维度	DP	贪心	分治
子问题关系	重叠	重叠（但只取最优的那一个）	不重叠
每步决策	枚举所有选项	直接取局部最优	拆分为子问题
正确性保证	最优子结构 + 重叠子问题	贪心选择性质	合并操作的正确性
时间复杂度	通常多项式	通常线性或 $O(n\log n)$	通常 $O(n\log n)$
难点	状态定义和转移方程	证明贪心选择性质	设计合并步骤

---

第 2 章 面试选型决策框架

2.1 问题结构识别流程

遇到一道算法题，按以下顺序思考：

第一步：判断是否是搜索/枚举问题

如果问题要求找所有解，或者无法定义”最优”，则用 BFS/DFS/回溯，不是 DP/贪心/分治。

第二步：判断是否有明显的分治结构

• 问题是否可以表达为”对左半/右半分别求解，然后合并”？
• 是否有”跨越中间”的情形需要特殊处理（如归并排序的逆序对，最大子数组的跨越中点情形）？
• 若是，考虑分治

第三步：判断是否能用贪心

• 是否有明显的”局部最优等于全局最优”的直觉？
• 是否能写出交换论证（假设 OPT 做了不同选择，证明交换后不变差）？
• 若是，尝试贪心并给出证明

第四步：如果上述都不行，考虑 DP

• 是否有最优子结构？（全局最优 = 某子问题最优 + 代价）
• 是否有重叠子问题？（同样的状态被重复计算）
• 若是，定义状态，写转移方程

2.2 贪心适用性速查表

场景	贪心策略	代表题目
区间选择（最多不重叠）	按右端点升序，贪心选	LeetCode 435
区间覆盖（最少箭头）	按右端点升序，贪心射	LeetCode 452
区间合并	按左端点升序，合并	LeetCode 56
可达范围维护	维护最远可达位置	LeetCode 55, 45
序列利润累积	正价差求和	LeetCode 122
环形路径	差分数组，累积量变负则重置	LeetCode 134
找零/资源分配	优先用稀缺资源	LeetCode 860
构造序列满足约束	排序决定插入顺序	LeetCode 406
任务调度（最少资源）	按开始时间排序 + 优先队列	经典活动调度
哈夫曼编码	最小堆，每次合并最小两个	LeetCode 1046 类

2.3 分治适用性速查表

场景	分治策略	代表题目
统计跨越分界点的量	归并分治，合并阶段统计	LeetCode 315, 493, 327
排序/选择	归并/快速排序，快速选择	LeetCode 215, 75
最大子数组	跨越中点三情形分治	LeetCode 53
树的路径/重建	递归分治，左子树/右子树/经过根	LeetCode 105, 543, 124
大整数/矩阵乘法	Karatsuba / Strassen	—

---

第 3 章 算法复杂度速查

3.1 分治算法复杂度（主定理 $T(n)=aT(n/b)+f(n)$）

情形	条件	复杂度	典型例子
叶主导	$f(n)=O(n^{{\log }_{b}a-ϵ})$	$O(n^{{\log }_{b}a})$	Karatsuba（$a=3,b=2$，$O(n^{1.585})$）
每层相等	$f(n)=\Theta (n^{{\log }_{b}a})$	$O(n^{{\log }_{b}a}\log n)$	归并排序（$a=2,b=2,f=n$，$O(n\log n)$）
根主导	$f(n)=\Omega (n^{{\log }_{b}a+ϵ})$	$O(f(n))$	二分查找（$a=1,b=2,f=1$，$O(\log n)$）

3.2 贪心算法复杂度

题目	时间复杂度	空间复杂度	主要开销
LeetCode 122（股票 II）	$O(n)$	$O(1)$	线性扫描
LeetCode 134（加油站）	$O(n)$	$O(1)$	线性扫描
LeetCode 860（找零）	$O(n)$	$O(1)$	线性扫描
LeetCode 406（队列重建）	$O(n^2)$	$O(n)$	链表插入
LeetCode 55（跳跃游戏 I）	$O(n)$	$O(1)$	线性扫描
LeetCode 45（跳跃游戏 II）	$O(n)$	$O(1)$	线性扫描
LeetCode 435（无重叠区间）	$O(n\log n)$	$O(1)$	排序
LeetCode 452（最少箭头）	$O(n\log n)$	$O(1)$	排序
LeetCode 56（合并区间）	$O(n\log n)$	$O(n)$	排序 + 结果存储

3.3 分治算法复杂度

题目	时间复杂度	空间复杂度	主要开销
LeetCode 315（右侧小数计数）	$O(n\log n)$	$O(n)$	归并分治
LeetCode 493（翻转对）	$O(n\log n)$	$O(n)$	归并分治
LeetCode 327（区间和计数）	$O(n\log n)$	$O(n)$	归并分治
LeetCode 75（颜色分类）	$O(n)$	$O(1)$	三路分区
LeetCode 215（第 K 大元素）	$O(n)$ 期望	$O(1)$	随机化快速选择
LeetCode 53（最大子数组）	$O(n\log n)$ 分治 / $O(n)$ Kadane	$O(\log n)$ / $O(1)$	—
LeetCode 105（从前/中序重建树）	$O(n)$	$O(n)$	哈希表 + 分治
LeetCode 543（二叉树直径）	$O(n)$	$O(h)$	DFS 分治
LeetCode 124（路径最大和）	$O(n)$	$O(h)$	DFS 分治

---

第 4 章 专栏高频错误盘点

4.1 分治类错误

错误 1：递推关系下标计算错误（LeetCode 105）

// 错误：直接用 inIndex，没有计算 leftSize
int leftSize = inIndex - inLeft;  // 左子树节点数
// 正确：前序中左子树的范围是 [preLeft+1, preLeft+leftSize]
//       后序中左子树的范围是 [postLeft, postLeft+leftSize-1]

记住：分治二叉树题的下标计算必须显式写出 leftSize = inIndex - inLeft，以此作为锚点计算所有范围。

错误 2：全局变量初始化错误

// 错误：maxDiameter 初始化为 Integer.MIN_VALUE（直径不可能为负）
int maxDiameter = Integer.MIN_VALUE;
 
// 正确：直径最小为 0（单节点到自身）
int maxDiameter = 0;

错误 3：主定理情形判断错误

主定理的三个情形用的是 $f(n)$ 与 $n^{{\log }_{b}a}$ 的大小比较（多项式意义），不是简单比较系数。

错误 4：Mermaid 图节点文本含空格未加双引号

// 错误
A[合并阶段统计] --> B[左子数组]

// 正确（文本含空格需要双引号）
A["合并阶段统计"] --> B["左子数组"]

4.2 贪心类错误

错误 5：区间排序用 a[1] - b[1]（整数溢出）

// 错误：可能整数溢出
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
 
// 正确
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

当 a[1] 是 Integer.MIN_VALUE，b[1] 是正数时，a[1] - b[1] 溢出为正数，导致排序错误。

错误 6：LeetCode 45 循环到 n-1 而非 n-2

// 错误：循环到 n-1，当最后一个位置恰好是 currentEnd 时多计一次跳跃
for (int i = 0; i < n; i++) { ... }
 
// 正确：只需循环到 n-2
for (int i = 0; i < n - 1; i++) { ... }

错误 7：LeetCode 435 vs 452 的重叠定义混淆

• 435：“不重叠”指 start >= lastEnd（端点相等不算重叠）
• 452：“需要新箭”指 start > arrowPos（端点相等时箭在边界，可以同时刺穿两者）

错误 8：贪心不成立的反例未考虑

常见错误：对 0/1 背包问题使用贪心（按价值/重量比排序），这是错误的。

0/1 背包不满足贪心选择性质（选了某件物品可能使后续物品放不下，导致总价值降低），必须使用 DP。分数背包满足，可以贪心。

错误 9：快速选择 pivot 未随机化

// 错误：固定选最后一个元素作为 pivot，在有序数组上退化为 O(n²)
int pivot = nums[right];
 
// 正确：随机选 pivot
int randIdx = left + (int)(Math.random() * (right - left + 1));
swap(nums, randIdx, right);
int pivot = nums[right];

4.3 通用编码错误

错误 10：链表插入用 ArrayList 而非 LinkedList（LeetCode 406）

ArrayList 在中间插入是 $O(n)$，但每次还要移动后续元素，常数更大。LinkedList.add(index, element) 在逻辑上是 $O(n)$（找位置需要遍历），实际插入 $O(1)$。面试中用 LinkedList 更合理地表达意图。

错误 11：二叉树分治返回值混淆全局变量

许多树的分治题需要一个函数返回”局部值”（如子树高度、子树最大路径），同时更新全局变量（如最终答案）。不要把两者混为一谈：

// 清晰的写法：返回局部值，更新全局变量
int dfs(TreeNode node) {
    // 局部值：子树的高度（用于父节点计算）
    // 全局变量 maxAnswer：最终答案
    if (node == null) return 0;
    int left = dfs(node.left);
    int right = dfs(node.right);
    maxAnswer = Math.max(maxAnswer, left + right);  // 更新全局
    return Math.max(left, right) + 1;               // 返回局部
}

---

第 5 章 面试实战策略

5.1 思路阐述顺序

面试中解题时，建议按以下顺序阐述：

1. 复述问题：用自己的话复述，确认理解正确
2. 暴力解法：先说出暴力解的思路和复杂度（展示你理解问题的全貌）
3. 优化方向：指出暴力解的瓶颈（哪里是 $O(n^2)$ 可以优化的）
4. 贪心/分治/DP 的选择：说出选择的理由（贪心选择性质、子问题独立性等）
5. 正确性论证：简要说明为什么贪心/分治是正确的（一句话的交换论证）
6. 实现代码：写代码时说出关键变量的含义
7. 复杂度分析：时间和空间复杂度
8. 边界情形：数组为空、全为负数、单元素等

5.2 贪心证明的快速表达

面试中不需要给出完整的数学证明，但需要有逻辑地说出核心论点：

活动选择/区间类：

“按右端点排序后，选择结束最早的活动是安全的——即使将它与最优解中不同的选择交换，贪心选到的区间结束不晚于最优解，给后续留的空间不少于最优解。通过归纳可以证明贪心每步都不比最优解差。”

跳跃游戏类：

“维护 maxReach 等价于跟踪 BFS 中当前层能到达的最远位置。每次扫描到 currentEnd（当前层末尾）时必须跳一次，farthest 成为新的层末尾。贪心的每一跳覆盖的范围不小于任何最优解的对应跳，因此跳数不多于最优解。“

5.3 常见追问及应对

追问：为什么不用 DP？

“这道题的贪心选择性质成立：每一步的局部最优选择（按右端点排序后选第一个）可以通过交换论证证明不会使全局变差，所以不需要枚举所有可能选择的 DP。贪心是 DP 的特例——当 DP 转移方程中最优的前驱状态可以直接确定（不需要遍历）时，DP 退化为贪心。”

追问：边界情形

• 数组为空：直接返回默认值（0 或 []）
• 单元素数组：通常返回 nums[0] 或 1
• 全为负数：最大子数组 = 最大的负数（Kadane 中 maxSum 初始化为 nums[0]，而非 0）

追问：空间复杂度是否可以优化？

对于分治类题目（如归并排序逆序对），通常无法避免 $O(n)$ 的额外空间（归并需要辅助数组）。对于贪心类题目，大多数可以 $O(1)$ 空间（只维护关键变量）。

---

第 6 章 专栏知识地图与学习路径

6.1 专栏覆盖的 LeetCode 题目

篇目	核心题目	考频	难度
01 分治基础	主定理理论（无题号）	—	—
02 归并分治	315, 493, 327	高	困难
03 快速排序	75, 215	极高	中等
04 最大子数组	53, 152, 918	极高	中/困难
05 树上分治	105, 106, 543, 124	极高	中/困难
06 贪心理论	分数背包（无题号）	—	—
07 跳跃游戏	55, 45	极高	中等
08 区间调度	435, 452, 56	极高	中等
09 股票与序列	122, 134, 860, 406	高	中等
10 综合通关	复习全部	—	—

6.2 推荐学习顺序

基础路线（约 2 周）： 01 → 03 → 04 → 05 → 06 → 07 → 08

强化路线（在基础上）： 02（归并分治统计）→ 09（贪心变体）→ 10（综合回顾）

冲刺路线（面试前 3 天）： 直接刷 07（跳跃游戏）、08（区间调度）、05（树路径）、03（快速选择），这四类是大厂面试最高频的分治/贪心题型。

6.3 继续深入的方向

分治进阶：

• 线段树分治（Segment Tree Divide and Conquer）：用于处理带撤销操作的问题
• CDQ 分治（陈丹琦分治）：处理三维偏序问题，$O(n{\log }^{2}n)$
• 点分治：图上路径统计问题

贪心进阶：

• 拟阵（Matroid）理论：贪心正确性的通用数学框架
• Dijkstra 算法：本质是一种贪心（每次选最短的未确定节点）
• Huffman 编码：贪心构造最优前缀码

---

第 7 章 本文核心结论

1. 贪心是 DP 的特例：当 DP 转移中最优前驱可以直接确定（不需要枚举）时，贪心成立。判断依据是交换论证：假设最优解做了不同选择，证明交换后不变差。

2. 分治的核心在合并步骤：子问题的拆分通常是自然的（左半右半），难点在于如何合并——统计跨越中点的量（归并统计逆序对）、合并两个子树的路径（树上分治）、合并两个有序段（归并排序）。

3. 面试选型的决策顺序：先看是否有分治结构（子问题独立可合并）→ 再看贪心是否可行（局部最优安全性）→ 最后才考虑 DP（枚举所有状态）。大多数分治/贪心题不需要 DP。

4. 六个最值得记忆的”模式-策略”对：

   • 区间选择/覆盖 → 按右端点排序
   • 区间合并 → 按左端点排序
   • 可达范围维护 → 维护 maxReach/farthest/currentEnd
   • 树上最优路径 → 递归返回局部值 + 全局变量记录答案
   • 归并分治统计 → 在合并阶段用双指针统计跨越分界点的量
   • 环形路径 → 差分数组 + 累积量变负时重置起始点

5. 两个最容易出 bug 的地方：区间排序用 Integer.compare 防溢出；LeetCode 45 循环到 n-2。这两个细节在面试中反复出现，务必在脑海中形成条件反射。