分治与贪心专栏导览：从框架到面试通关

专栏定位

本专栏面向有一定编程基础、正在备战技术面试的工程师。讨论范围严格限定于分治法与贪心算法两大设计范式，不涉及动态规划、回溯、图算法等其他领域。

核心目标：帮助读者真正理解分治与贪心的设计哲学，而非死记硬背套路。每道题的讲解遵循”是什么 → 为什么出现 → 不这样会怎样 → 如何落地 → 边界与反例”的推导链，力求通俗易懂而不失深度。

专栏目录

序号	文章标题	核心话题	覆盖 LeetCode 题目
01	分治法基础：递归树与主定理——分治的思维骨架	分治三要素、递归树分析、主定理三种情况、分治框架模板	概念篇（Merge Sort、Binary Search 为例）
02	归并分治精讲：逆序对的多种面孔	归并计数思想、树状数组对比、离散化技巧	Count of Smaller Numbers After Self（315）、Reverse Pairs（493）、Count of Range Sum（327）
03	快速排序分治框架：分区的力量	Lomuto/Hoare 分区、随机化枢轴、三路分区、快速选择	Kth Largest Element in an Array（215）、Sort Colors（75）
04	最大子数组问题：Kadane 算法与分治视角	Kadane 动态思想、分治跨界解法、环形子数组变形	Maximum Subarray（53）、Maximum Product Subarray（152）、Maximum Sum Circular Subarray（918）
05	分治在二叉树：重建与最长路径	先序/后序重建、哈希加速定位、直径与路径收益	Construct Binary Tree from Preorder and Inorder（105）、Construct Binary Tree from Inorder and Postorder（106）、Diameter of Binary Tree（543）、Binary Tree Maximum Path Sum（124）
06	贪心算法：从直觉到证明的严格之路	贪心正确性证明（交换论证法、数学归纳法）、与 DP 的边界	Activity Selection、Fractional Knapsack（概念篇）
07	跳跃游戏系列：维护可达区间的贪心艺术	最远可达边界思想、最少跳跃次数的分段贪心、BFS 类比	Jump Game（55）、Jump Game II（45）
08	区间调度贪心精讲：覆盖、不重叠与最少箭头	按结束时间排序、不重叠区间计数、最少点覆盖的等价性	Non-overlapping Intervals（435）、Minimum Number of Arrows to Burst Balloons（452）、Merge Intervals（56）
09	股票与序列贪心：多次交易、加油站与柠檬水找零	峰谷累积贪心、环形数组差分贪心、模拟贪心	Best Time to Buy and Sell Stock II（122）、Gas Station（134）、Lemonade Change（860）、Queue Reconstruction by Height（406）
10	综合通关：分治与贪心的选型模式与面试总结	分治 vs 贪心 vs DP 三角关系、模式识别、复杂度速查、高频错误盘点	综合复习篇

专栏阅读建议

第 01 篇必读：递归树分析与主定理是理解所有分治算法复杂度的基础，不能跳过
分治篇（02-05）：重点理解”归并计数”和”树上分治”两种核心模式，它们覆盖了绝大多数分治面试题
第 06 篇是贪心的根基：贪心算法的核心难点不在实现，而在正确性证明，第 06 篇给出的两种证明方法（交换论证法、数学归纳法）是通关贪心题的关键
贪心篇（07-09）：三篇各代表一种贪心模式——可达范围维护、按排序策略消除冲突、局部最优累积
本专栏不覆盖：动态规划（虽然贪心常被误认为是 DP 的特例，但本专栏仅讨论严格的贪心证明）、回溯搜索

分治与贪心算法复杂度速查

分治代表算法

算法	时间复杂度	空间复杂度	主定理形式
归并排序	$O (n lo g n)$	$O (n)$	$T (n) = 2 T (n /2) + O (n)$ ，情形 2
快速排序（平均）	$O (n lo g n)$	$O (lo g n)$	随机化期望
快速排序（最坏）	$O (n^{2})$	$O (n)$	每次 partition 极不平衡
快速选择（平均）	$O (n)$	$O (lo g n)$	$T (n) = T (n /2) + O (n)$ ，情形 3
二分查找	$O (lo g n)$	$O (1)$	$T (n) = T (n /2) + O (1)$ ，情形 2
逆序对计数	$O (n lo g n)$	$O (n)$	归并排序同形
Karatsuba 大数乘法	$O (n^{1.585})$	$O (n)$	$T (n) = 3 T (n /2) + O (n)$ ，情形 1

贪心代表算法

算法	时间复杂度	正确性依赖
活动选择（按结束时间排序）	$O (n lo g n)$	局部最优保证全局最优（可证明）
跳跃游戏（最少步数）	$O (n)$	可达边界单调不减
区间最少点覆盖	$O (n lo g n)$	等价于最大不相交区间集
Huffman 编码	$O (n lo g n)$	最优前缀码（可证明）
Dijkstra 最短路	$O ((V + E) lo g V)$	非负权边条件下的贪心松弛
Kruskal/Prim 最小生成树	$O (E lo g E)$	割性质与圈性质（可证明）

两种范式的本质对比

维度	分治法	贪心算法
核心思想	分解 → 递归求解子问题 → 合并	每步选择局部最优，不回溯
子问题关系	子问题相互独立，无重叠	不显式划分子问题
正确性来源	归纳法：子问题正确则整体正确	需证明贪心选择性质成立
常见应用	排序、查找、树形结构、几何	调度、覆盖、编码、图论
时间复杂度	通常 $O (n lo g n)$ 或 $O (n^{1 + ϵ})$	通常 $O (n lo g n)$ （排序后线性扫描）
与 DP 的关系	子问题独立，无重叠，不需要 memo	是 DP 的特例（每步选择唯一）