刷题刷到一定阶段你会发现有一类“乱序求极值”问题特别唬人给你一组东西顺序随便你排然后让你求某个指标的最大或最小值。我第一次遇到这种题时第一反应是枚举全排列看到数据范围 (n10^5) 直接傻眼。后来学会贪心里一个非常漂亮的工具——相邻交换法这类题才从“噩梦”变成“套路”。今天这篇算法日记想把相邻交换法从头到尾讲透顺便聊聊跳跃游戏2这个经典贪心题看看它和相邻交换法到底差在哪。这篇内容不挑基础。哪怕你只是刚学完贪心概念也能照着推导如果你在准备面试里面给的证明模板可以直接套用。我会先讲识别问题的特征再给相邻交换法的完整证明骨架然后用两道实战题带出代码和暴力验证最后记录几个我踩过的坑。整篇没有高深数学最多就是小学奥数级别的比较大小。1. 先识别“乱序求极值”这类题到底长什么样1.1 三个特征帮你一眼认出来我总结过能用相邻交换法解决的问题通常同时满足三个特征。第一输入是一堆“元素”并且这些元素可以任意排列。注意“任意排列”很关键如果题目本身规定了输入顺序不能动那大概率不是这个套路。第二目标是求某个表达式的最大值或最小值比如总等待时间最小、总代价最大。第三最终的答案可以通过“把这堆元素按某个规则排序”得到。也就是说你不需要动态规划不需要搜索排序就是答案。拿最经典的排队接水问题举例有 n 个人排队第 i 个人接水需要time[i]分钟问怎么排队能让所有人的等待时间总和最小。每个人都能排到任意位置目标是最小化总和答案就是按time[i]从小到大排。这三个特征它全占了。但你可能会问光知道“排序就是答案”有什么用难的是怎么确定排什么序。如果是按一个属性升序或降序那还好说万一排序规则是两个属性的比值甚至是一个自定义的比较器靠猜就很容易翻车。相邻交换法就是用来解决这个“怎么排”的问题的。1.2 枚举和动态规划为什么都不太对劲遇到排列类问题新手最常见的思路是枚举全排列。枚举确实不会错但复杂度是 O(n!)。只要 n 超过 10基本就跑不动了而这类题的数据范围动辄 (10^4) 甚至 (10^5)枚举纯属送命。还有人会想到动态规划。DP 在处理“有状态限制”的排列问题时确实能派上用场比如经典的“状态压缩 DP”可以将复杂度压到 O(2^n * n)但 n20 已经是极限。更何况乱序求极值问题里很多场景根本没有额外状态目标函数只跟“相邻关系”有关。这时候你用 DP属于拿大炮打蚊子不仅写起来累还容易把状态定义错。所以从复杂度上看最优解几乎一定是贪心加排序把 O(n!) 或者 O(2^n) 的复杂度直接降到 O(n log n)。但这里就出现了一个灵魂问题贪心的排序规则怎么证明这也是为什么很多人排序策略靠猜猜对了 AC猜错了 debug 到怀疑人生。1.3 先排序再验证我常用的入手姿势我自己的做题习惯是拿到一个疑似乱序求极值的题先不急着证明。先找最简单的两个元素手算一下“如果 A 在 B 前面”和“如果 B 在 A 前面”两种方案的代价差然后看能不能把这个差值写成一个只跟 A、B 有关的比较式。如果差值可以写成类似 (a b) 或者 (a/b c/d) 的形式那就说明排序规则基本找到了。接下来我会先写一个暴力枚举的小脚本对 n 比较小的随机数据验证这个规则验证通过后再去写正式解法。这个过程看起来多了一步实际上省了很多时间——因为排序规则一旦猜错后面的代码写得再漂亮也是白搭。2. 相邻交换法一个极其优雅的贪心证明工具2.1 核心动作拿相邻的两个元素算一笔交换账相邻交换法的核心思想非常朴素既然最终答案对应一个排列那我就看这个排列里的任意相邻两个元素。如果交换它们俩会让目标函数变得更优那说明当前排列不是最优的应该交换。如果无论怎么交换当前顺序都已经不会更优那这个排列就是局部最优并且在一定条件下就是全局最优。听起来有点像冒泡排序对不对其实本质就是一回事。冒泡排序就是不断比较相邻元素决定是否交换最后得到一个有序序列。相邻交换法只不过是把“比较规则”变成了“交换后目标函数是否变优”。假设当前相邻两个元素是 A 和 B前面已经排好了一部分元素后面的元素暂时不看。我们可以分别算出“A 在前B 在后”和“B 在前A 在后”两种顺序下目标函数关于 A、B 的代价部分。然后比较这两部分的大小。如果前者更小就说明 A 应该排在 B 前面如果后者更小说明 B 应该排在 A 前面。这个比较结果就是最终的排序规则。2.2 严格化证明的五步模板很多算法书把相邻交换法写得神乎其神其实剥开来看就是一个五步模板。第一步假设最优排列为 P随便挑其中相邻的两个元素 X 和 Y并且假设 X 在 Y 前面。第二步把这两个元素交换位置得到一个新排列 P。第三步写出 P 和 P 的目标函数表达式注意大部分项都一样只有涉及 X、Y 以及它们之间顺序的项不同。第四步令“交换前代价 - 交换后代价 0”解出 X 应该在 Y 前面的条件。第五步验证这个条件满足传递性于是可以把它作为排序的比较器排序后得到的就是最优排列。这个模板看起来简单但第五步特别容易被忽略。比较规则如果不满足传递性比如出现“A 该排在 B 前B 该排在 C 前C 又该排在 A 前”的循环那排序根本没法做。所以你在推完比较式后一定要确认它符合“严格弱序”反自反、非对称、可传递。幸运的是绝大多数从相邻交换法推出来的规则都是基于实数大小比较天然满足这些性质。2.3 从比较规则到最终代码中间还有一道坎推出比较规则后你还要把它转成代码。编程语言里的排序函数比如 Python 的sort、C 的std::sort都要求比较器是严格弱序。如果你推出来的规则是“当 (a b) 时 a 排在前面”那直接用默认排序或者keylambda x: ...就行。但有的时候比较规则不是单个属性而是一个比值比如 (a.time / a.cost b.time / b.cost)。这时你要么用functools.cmp_to_key传自定义比较器要么用分数交叉相乘也就是写成a.time * b.cost b.time * a.cost。我强烈建议用交叉相乘因为直接做浮点除法在大数据下会有精度问题而且排序比较器要求严格一致性浮点误差可能导致结果不稳定。3. 实战排队等待时间最小化与任务调度问题3.1 排队接水最简单的相邻交换模型来一个最经典的例子。有 n 个人排队接水第 i 个人接水需要time[i]分钟。每个人从开始排队到接完水总共等待的时间等于前面所有人的接水时间之和再加上自己接水的时间。问怎么排队能让所有人的等待时间总和最小。假设当前已经排了一部分人他们总共需要 T 分钟。现在相邻有两个人 A 和 B接水时间分别是 a 和 b。如果 A 排在 B 前面那么 A 的等待时间是 (T a)B 的等待时间是 (T a b)这一小段的总代价是 ((T a) (T a b) 2T 2a b)。如果交换成 B 排在 A 前面总代价就变成 ((T b) (T b a) 2T 2b a)。比较一下A 在前的代价更小当且仅当 (2T 2a b 2T 2b a)也就是 (a b)。所以按接水时间从小到大排序能保证总等待时间最小。注意这里的“等待时间”是从开始排队到接完水为止。如果题意变成“从开始排队到开始接水”那每个人的等待时间会少掉自己接水的那部分推导中会差一项但最终排序结论仍然是按time升序。这种定义差异就是讨论区经常吵起来的根源做题前一定看清题面。3.2 任务罚款问题当排序规则变成一个比值排队接水太简单了我们加大一点难度。假设有 n 个任务每个任务有耗时cost[i]和单位时间罚款penalty[i]。任务只能一个一个做一旦某个任务晚开始一个单位时间就要多付penalty[i]这么多罚款。现在要确定任务执行顺序让总罚款最小。这个问题的直觉就不那么明显了。有人觉得耗时短的先做有人觉得罚款多的先做但正确答案是看“性价比”。我们同样用相邻交换法推。假设当前相邻两个任务 X 和 Y耗时分别为 x_time、y_time罚款率分别为 x_p、y_p。如果 X 先做那么 Y 会比 X 后做晚 x_time 个时间单位因此 Y 的罚款会增加x_time * y_p反过来X 自己不会因为顺序多罚款。同理如果 Y 先做X 的罚款会增加y_time * x_p。X 先做更优的条件是[ x_time \times y_p y_time \times x_p ]整理一下就是[ \frac{x_time}{x_p} \frac{y_time}{y_p} ]也就是按“耗时 / 罚款率”升序排列。这个结论光靠直觉很难直接想到但用相邻交换法几十秒就能推出来。3.3 用暴力枚举验证你的排序规则排序规则推出来后我在正式写题前通常会做一个暴力对拍。做法很简单生成一个长度不超过 8 的随机数组用itertools.permutations枚举所有排列算出最优值再把同样数据丢进按排序规则写的贪心函数里比较结果。如果随机测了很多组都一样基本可以放心。这里给一个排队接水问题的验证代码from itertools import permutations import random def brute(arr): n len(arr) best float(inf) for perm in permutations(arr): total 0 cur 0 for t in perm: total cur t # 等待到接完水 cur t best min(best, total) return best def greedy(arr): # 按耗时升序排列 s sorted(arr) total 0 cur 0 for t in s: total cur t cur t return total for _ in range(1000): arr [random.randint(1, 20) for _ in range(random.randint(1, 8))] if brute(arr) ! greedy(arr): print(错误, arr) break else: print(所有随机用例通过)这个对拍脚本我几乎每道题都会写尤其是遇到“看起来像排序但排序规则不太好想”的题。它不能代替证明但能在你思路出错时快速暴露问题。3.4 实现细节与复杂度分析两个实战题的最终复杂度都是 O(n log n)瓶颈在排序。前面排队接水的代码可以直接对数组排序后累加任务罚款问题则可以构造一个包含cost和penalty的元组列表然后通过自定义比较规则排序。在 Python 里处理“按比值排序”我推荐用functools.cmp_to_key但要注意比较器性能。cmp_to_key比key慢所以如果能用key表达就尽量用key。像任务罚款这个例子虽然它是比值排序但你无法直接用单个 key 完成因为比较需要同时看到两个任务的数据所以cmp_to_key是合理的。另一个细节是数据范围。cost和penalty都可能达到 (10^9)直接计算cost / penalty会有精度问题交叉相乘cost1 * penalty2可能超过 32 位整数所以 Python 虽然没这个问题但在 C 里要开long long。这个坑我踩过一次线上全 WA最后发现是溢出。4. 再看跳跃游戏2不是乱序但贪心思路一脉相承4.1 题目描述与常见误解跳跃游戏2是 LeetCode 上非常经典的贪心题给定一个非负整数数组nums你初始站在下标 0nums[i]表示你从下标 i 最多能往后跳多远。问跳到最后一个下标最少需要跳几次。注意这个题和前面的“乱序求极值”有本质区别数组顺序是固定的你不能重新排列元素。所以它不适用相邻交换法。但它是贪心思想里另一个重要分支——区间覆盖式贪心。很多初学者会误以为“每次选择能跳得最远的那个位置”这其实是错的。我见过有人拿[2, 3, 1, 1, 4]举例从 0 开始第一步如果贪心跳最远到下标 2再跳只能到下标 3最后还要一步到下标 4总共 3 步但最优解是先从 0 跳到下标 1再直接跳到末尾只需要 2 步。所以“能跳最远”不等于“这一步走得最远”。正确的贪心策略是在当前位置能覆盖的范围内先不要急着跳而是遍历这个范围内所有位置记录“从这些位置再跳一次能到达的最远位置”。当你走到当前覆盖范围的边界时不得不跳一次这时再跳并把下一段覆盖范围更新成刚才记录的最远位置。这样每一步都让下一次的覆盖范围最大化跳跃次数自然最少。4.2 区间覆盖式的贪心证明为什么这个策略是对的我们可以用数学归纳法来想。假设当前已经跳了 k 步能覆盖的范围是 ([0, end])。在这个范围内任意位置 j 都是可达的。对于任意 j从 j 出发一步能到达的最远位置是 (j nums[j])。我们选择在到达 end 时跳跃并且下一次起点一定落在 ([0, end]) 内而这一步能到达的最远距离就是[ \max_{0 \le j \le end} (j nums[j]) ]这个最大值其实就是下一次跳跃后的覆盖范围右端点。如果存在一种 k1 步的方案能覆盖更远那一定是因为它从某个 j 出发达到了更远的位置但我们的 max 已经把范围内所有 j 都考虑到了所以不存在比这个更远的 k1 步方案。每一步都取到理论最大值最终总步数就是最小的。这个证明思路其实也带着“贪心选择性质”的味道局部最远覆盖全局最优步数。它和相邻交换法的区别在于相邻交换法证明的是“两个元素谁先谁后”而区间覆盖贪心证明的是“每一步的覆盖范围可以取到上界”。4.3 Python 代码与边界测试跳跃游戏2的标准写法可以省掉 DP只用一次遍历。下面是我实际在用的版本def jump(nums): n len(nums) if n 1: return 0 max_pos 0 # 当前这一步能够到达的最远位置 end 0 # 当前这一步的覆盖边界 steps 0 # 已经跳的次数 for i in range(n - 1): # 遍历当前位置能覆盖的区间更新下一步能到的最远位置 max_pos max(max_pos, i nums[i]) # 走到了当前覆盖范围的边界必须再跳一次 if i end: steps 1 end max_pos if end n - 1: break return steps有几个边界值得注意。第一n 1时直接返回 0因为已经在终点。第二循环只走到n - 2不需要遍历最后一个位置因为到了终点就不需要再跳了。第三end n - 1提前退出能省下不必要遍历。题目保证一定能到达终点所以不需要额外判断失败但如果是自己写测试可以加一个防御性检查。如果你把[2, 3, 1, 1, 4]丢进去运行结果是 2。过程是从下标 0覆盖范围 [0, 0]遍历到 index 0 时max_pos 2遇到边界i endsteps1end2。然后遍历 index 1 时max_pos max(2, 13) 4index 2 时max_pos max(4, 21) 4当i endi2时steps2end4已经到达末尾返回 2。4.4 面试现场怎么把两道题串起来讲如果你在面试中被问到跳跃游戏2很多人的第一反应是往 DP 上想。确实dp[i] min(dp[j] 1)也能做但复杂度是 O(n^2)遇到大数据就挂了。面试官更想听到的其实是你能识别出这是“区间覆盖贪心”而不是“排序贪心”。我建议的讲解节奏是先说明这个题不能排序因为数组顺序固定再用“最小跳跃次数”转化为“每步扩展覆盖区间”最后写代码。如果面试官追问怎么证明就用上面那个“上界”论证。反过来如果面试官先问“排队接水”这类题你就可以引出相邻交换法然后对比说“跳跃游戏2 是另一种贪心核心不是交换顺序而是每一步覆盖范围最大化”。这样既展示了你对不同贪心模型的区分能力也让整个回答更有层次。5. 踩坑记录与常见问题排查5.1 为什么交换相邻两项能推出全局最优最容易被问懵的点很多初学者用相邻交换法时心里一直有个疑问我只证明了“相邻交换不会让结果变差”但凭什么说最终排序就是全局最优答案藏在“任意排列都可以通过有限次相邻交换变成目标排列”这件事里。假设你推导出比较规则 R并且 R 满足严格弱序那么对任何一个不是按 R 排序的排列一定存在至少一对相邻元素违反了 R 的顺序。交换这一对相邻元素目标函数不会变差。反复进行这样的交换最终你会得到一个按 R 排序的排列而且每一步都不会让目标函数变差。也就是说排序后的结果至少不比任何一个初始排列差所以它就是全局最优。这个论证里最容易翻车的地方是比较规则 R 必须满足严格弱序。如果 R 不满足传递性那“反复交换直到有序”的过程可能永远不会收敛或者收敛到某个局部最优但全局不是最优。所以用相邻交换法最后一定要花 30 秒确认传递性。5.2 相邻交换法失效的典型场景不是所有“顺序可变求极值”都适合相邻交换法。我总结过三类失效场景。第一目标函数不只是相邻两项的代价还依赖全局状态。比如某些调度问题后面任务的等待时间不仅取决于前一个任务还取决于所有已完成任务的总耗时。这种情况下相邻两项交换时后面所有任务的代价都会变不能只比较两个元素。第二题目对排列有额外约束比如要求某些任务必须在某些任务之前或者有资源上限单纯排序解决不了需要 DP 或搜索。第三比较规则不满足传递性。这个刚才说过一旦出现循环比较排序直接失效。我之前做一个带截止日期的任务调度问题用相邻交换法推出“按截止时间排序”结果提交 WA。后来发现题里还要求如果任务超时罚款是阶梯式增长不是线性增长这会导致交换后对后续任务的影响无法忽略。这时候正确的解法是贪心优先队列而不是纯排序。5.3 调试用的数据生成器和暴力对拍遇到排序策略不确定的题我强烈建议写一个数据生成器加暴力对拍脚本。做法也很简单随机生成长度在 1 到 8 之间的测试数据用permutations枚举所有排列算出精确答案再和你排序后的结果对比。关键点是生成数据时不要只生成“均匀随机”的整数要覆盖边界情况。比如任务罚款问题让某些cost和penalty相同让某些cost为 0如果题目允许让某些值特别大、特别小。这些边界最容易让浮点比较或者溢出问题现出原形。如果暴力对拍挂了不要急着改贪心规则。先把挂掉的那组数据打出来手工跑一遍相邻交换推导看看是不是漏了什么项。很多时候问题出在目标函数定义上比如你算代价时少算了“当前时间”这一项。所以对拍脚本里暴力函数和贪心函数必须用同一个代价公式否则就是拿着两把不一样的尺子量东西。5.4 几个容易忽略的实现细节先说比较器。Python 的sort默认只接受key函数如果你要用自定义比较器需要functools.cmp_to_key。但cmp_to_key的返回值要让cmp(a, b)返回负数表示a b这个方向特别容易搞反。我每次写完都会先用三个元素的手工用例验一下排序结果确认方向对了再提交。再说整数溢出和精度。只要是比值排序一律用交叉相乘不要用浮点除法。C 里要注意乘积可能超过 int 范围开long longPython 虽然没有溢出问题但浮点除法依然可能因为精度问题造成排序不稳定。我之前测试过一组cost10^9, penalty1和cost1, penalty10^9的数据用浮点除法在极端情况下结果会错。还有一个细节是“相等元素怎么处理”。相邻交换法推导出的规则往往只给出严格小于关系如果两个元素相等谁前谁后其实无所谓。但你要确保比较器对相等元素返回 0不然 C 的std::sort可能触发未定义行为Python 的cmp_to_key则可能效率变差。最稳妥的做法是推导出严格比较规则后在比较器里把相等情况显式返回 0。我在实际刷题中养成了一个习惯凡是遇到“顺序可变、求极值”的题先试着用相邻交换法推两个元素的交换条件推得出来并且满足传递性就大胆写排序推不出来再往 DP、贪心优先队列这些方向考虑。这个判断过程可能只要几分钟却能在后面省下大量 debug 时间。跳跃游戏2这种“顺序固定”的贪心题我也会用类似思路去想想每一步的局部最优能不能达到全局上界能就用不能就找反例。说到底贪心不是靠猜而是靠“局部调整不劣”或者“覆盖范围上界可达”这类理由把每一步的选择钉死。希望这篇算法日记能让你少走一些我走过的弯路。
相邻交换法详解：从贪心排序证明到跳跃游戏2的对比
刷题刷到一定阶段你会发现有一类“乱序求极值”问题特别唬人给你一组东西顺序随便你排然后让你求某个指标的最大或最小值。我第一次遇到这种题时第一反应是枚举全排列看到数据范围 (n10^5) 直接傻眼。后来学会贪心里一个非常漂亮的工具——相邻交换法这类题才从“噩梦”变成“套路”。今天这篇算法日记想把相邻交换法从头到尾讲透顺便聊聊跳跃游戏2这个经典贪心题看看它和相邻交换法到底差在哪。这篇内容不挑基础。哪怕你只是刚学完贪心概念也能照着推导如果你在准备面试里面给的证明模板可以直接套用。我会先讲识别问题的特征再给相邻交换法的完整证明骨架然后用两道实战题带出代码和暴力验证最后记录几个我踩过的坑。整篇没有高深数学最多就是小学奥数级别的比较大小。1. 先识别“乱序求极值”这类题到底长什么样1.1 三个特征帮你一眼认出来我总结过能用相邻交换法解决的问题通常同时满足三个特征。第一输入是一堆“元素”并且这些元素可以任意排列。注意“任意排列”很关键如果题目本身规定了输入顺序不能动那大概率不是这个套路。第二目标是求某个表达式的最大值或最小值比如总等待时间最小、总代价最大。第三最终的答案可以通过“把这堆元素按某个规则排序”得到。也就是说你不需要动态规划不需要搜索排序就是答案。拿最经典的排队接水问题举例有 n 个人排队第 i 个人接水需要time[i]分钟问怎么排队能让所有人的等待时间总和最小。每个人都能排到任意位置目标是最小化总和答案就是按time[i]从小到大排。这三个特征它全占了。但你可能会问光知道“排序就是答案”有什么用难的是怎么确定排什么序。如果是按一个属性升序或降序那还好说万一排序规则是两个属性的比值甚至是一个自定义的比较器靠猜就很容易翻车。相邻交换法就是用来解决这个“怎么排”的问题的。1.2 枚举和动态规划为什么都不太对劲遇到排列类问题新手最常见的思路是枚举全排列。枚举确实不会错但复杂度是 O(n!)。只要 n 超过 10基本就跑不动了而这类题的数据范围动辄 (10^4) 甚至 (10^5)枚举纯属送命。还有人会想到动态规划。DP 在处理“有状态限制”的排列问题时确实能派上用场比如经典的“状态压缩 DP”可以将复杂度压到 O(2^n * n)但 n20 已经是极限。更何况乱序求极值问题里很多场景根本没有额外状态目标函数只跟“相邻关系”有关。这时候你用 DP属于拿大炮打蚊子不仅写起来累还容易把状态定义错。所以从复杂度上看最优解几乎一定是贪心加排序把 O(n!) 或者 O(2^n) 的复杂度直接降到 O(n log n)。但这里就出现了一个灵魂问题贪心的排序规则怎么证明这也是为什么很多人排序策略靠猜猜对了 AC猜错了 debug 到怀疑人生。1.3 先排序再验证我常用的入手姿势我自己的做题习惯是拿到一个疑似乱序求极值的题先不急着证明。先找最简单的两个元素手算一下“如果 A 在 B 前面”和“如果 B 在 A 前面”两种方案的代价差然后看能不能把这个差值写成一个只跟 A、B 有关的比较式。如果差值可以写成类似 (a b) 或者 (a/b c/d) 的形式那就说明排序规则基本找到了。接下来我会先写一个暴力枚举的小脚本对 n 比较小的随机数据验证这个规则验证通过后再去写正式解法。这个过程看起来多了一步实际上省了很多时间——因为排序规则一旦猜错后面的代码写得再漂亮也是白搭。2. 相邻交换法一个极其优雅的贪心证明工具2.1 核心动作拿相邻的两个元素算一笔交换账相邻交换法的核心思想非常朴素既然最终答案对应一个排列那我就看这个排列里的任意相邻两个元素。如果交换它们俩会让目标函数变得更优那说明当前排列不是最优的应该交换。如果无论怎么交换当前顺序都已经不会更优那这个排列就是局部最优并且在一定条件下就是全局最优。听起来有点像冒泡排序对不对其实本质就是一回事。冒泡排序就是不断比较相邻元素决定是否交换最后得到一个有序序列。相邻交换法只不过是把“比较规则”变成了“交换后目标函数是否变优”。假设当前相邻两个元素是 A 和 B前面已经排好了一部分元素后面的元素暂时不看。我们可以分别算出“A 在前B 在后”和“B 在前A 在后”两种顺序下目标函数关于 A、B 的代价部分。然后比较这两部分的大小。如果前者更小就说明 A 应该排在 B 前面如果后者更小说明 B 应该排在 A 前面。这个比较结果就是最终的排序规则。2.2 严格化证明的五步模板很多算法书把相邻交换法写得神乎其神其实剥开来看就是一个五步模板。第一步假设最优排列为 P随便挑其中相邻的两个元素 X 和 Y并且假设 X 在 Y 前面。第二步把这两个元素交换位置得到一个新排列 P。第三步写出 P 和 P 的目标函数表达式注意大部分项都一样只有涉及 X、Y 以及它们之间顺序的项不同。第四步令“交换前代价 - 交换后代价 0”解出 X 应该在 Y 前面的条件。第五步验证这个条件满足传递性于是可以把它作为排序的比较器排序后得到的就是最优排列。这个模板看起来简单但第五步特别容易被忽略。比较规则如果不满足传递性比如出现“A 该排在 B 前B 该排在 C 前C 又该排在 A 前”的循环那排序根本没法做。所以你在推完比较式后一定要确认它符合“严格弱序”反自反、非对称、可传递。幸运的是绝大多数从相邻交换法推出来的规则都是基于实数大小比较天然满足这些性质。2.3 从比较规则到最终代码中间还有一道坎推出比较规则后你还要把它转成代码。编程语言里的排序函数比如 Python 的sort、C 的std::sort都要求比较器是严格弱序。如果你推出来的规则是“当 (a b) 时 a 排在前面”那直接用默认排序或者keylambda x: ...就行。但有的时候比较规则不是单个属性而是一个比值比如 (a.time / a.cost b.time / b.cost)。这时你要么用functools.cmp_to_key传自定义比较器要么用分数交叉相乘也就是写成a.time * b.cost b.time * a.cost。我强烈建议用交叉相乘因为直接做浮点除法在大数据下会有精度问题而且排序比较器要求严格一致性浮点误差可能导致结果不稳定。3. 实战排队等待时间最小化与任务调度问题3.1 排队接水最简单的相邻交换模型来一个最经典的例子。有 n 个人排队接水第 i 个人接水需要time[i]分钟。每个人从开始排队到接完水总共等待的时间等于前面所有人的接水时间之和再加上自己接水的时间。问怎么排队能让所有人的等待时间总和最小。假设当前已经排了一部分人他们总共需要 T 分钟。现在相邻有两个人 A 和 B接水时间分别是 a 和 b。如果 A 排在 B 前面那么 A 的等待时间是 (T a)B 的等待时间是 (T a b)这一小段的总代价是 ((T a) (T a b) 2T 2a b)。如果交换成 B 排在 A 前面总代价就变成 ((T b) (T b a) 2T 2b a)。比较一下A 在前的代价更小当且仅当 (2T 2a b 2T 2b a)也就是 (a b)。所以按接水时间从小到大排序能保证总等待时间最小。注意这里的“等待时间”是从开始排队到接完水为止。如果题意变成“从开始排队到开始接水”那每个人的等待时间会少掉自己接水的那部分推导中会差一项但最终排序结论仍然是按time升序。这种定义差异就是讨论区经常吵起来的根源做题前一定看清题面。3.2 任务罚款问题当排序规则变成一个比值排队接水太简单了我们加大一点难度。假设有 n 个任务每个任务有耗时cost[i]和单位时间罚款penalty[i]。任务只能一个一个做一旦某个任务晚开始一个单位时间就要多付penalty[i]这么多罚款。现在要确定任务执行顺序让总罚款最小。这个问题的直觉就不那么明显了。有人觉得耗时短的先做有人觉得罚款多的先做但正确答案是看“性价比”。我们同样用相邻交换法推。假设当前相邻两个任务 X 和 Y耗时分别为 x_time、y_time罚款率分别为 x_p、y_p。如果 X 先做那么 Y 会比 X 后做晚 x_time 个时间单位因此 Y 的罚款会增加x_time * y_p反过来X 自己不会因为顺序多罚款。同理如果 Y 先做X 的罚款会增加y_time * x_p。X 先做更优的条件是[ x_time \times y_p y_time \times x_p ]整理一下就是[ \frac{x_time}{x_p} \frac{y_time}{y_p} ]也就是按“耗时 / 罚款率”升序排列。这个结论光靠直觉很难直接想到但用相邻交换法几十秒就能推出来。3.3 用暴力枚举验证你的排序规则排序规则推出来后我在正式写题前通常会做一个暴力对拍。做法很简单生成一个长度不超过 8 的随机数组用itertools.permutations枚举所有排列算出最优值再把同样数据丢进按排序规则写的贪心函数里比较结果。如果随机测了很多组都一样基本可以放心。这里给一个排队接水问题的验证代码from itertools import permutations import random def brute(arr): n len(arr) best float(inf) for perm in permutations(arr): total 0 cur 0 for t in perm: total cur t # 等待到接完水 cur t best min(best, total) return best def greedy(arr): # 按耗时升序排列 s sorted(arr) total 0 cur 0 for t in s: total cur t cur t return total for _ in range(1000): arr [random.randint(1, 20) for _ in range(random.randint(1, 8))] if brute(arr) ! greedy(arr): print(错误, arr) break else: print(所有随机用例通过)这个对拍脚本我几乎每道题都会写尤其是遇到“看起来像排序但排序规则不太好想”的题。它不能代替证明但能在你思路出错时快速暴露问题。3.4 实现细节与复杂度分析两个实战题的最终复杂度都是 O(n log n)瓶颈在排序。前面排队接水的代码可以直接对数组排序后累加任务罚款问题则可以构造一个包含cost和penalty的元组列表然后通过自定义比较规则排序。在 Python 里处理“按比值排序”我推荐用functools.cmp_to_key但要注意比较器性能。cmp_to_key比key慢所以如果能用key表达就尽量用key。像任务罚款这个例子虽然它是比值排序但你无法直接用单个 key 完成因为比较需要同时看到两个任务的数据所以cmp_to_key是合理的。另一个细节是数据范围。cost和penalty都可能达到 (10^9)直接计算cost / penalty会有精度问题交叉相乘cost1 * penalty2可能超过 32 位整数所以 Python 虽然没这个问题但在 C 里要开long long。这个坑我踩过一次线上全 WA最后发现是溢出。4. 再看跳跃游戏2不是乱序但贪心思路一脉相承4.1 题目描述与常见误解跳跃游戏2是 LeetCode 上非常经典的贪心题给定一个非负整数数组nums你初始站在下标 0nums[i]表示你从下标 i 最多能往后跳多远。问跳到最后一个下标最少需要跳几次。注意这个题和前面的“乱序求极值”有本质区别数组顺序是固定的你不能重新排列元素。所以它不适用相邻交换法。但它是贪心思想里另一个重要分支——区间覆盖式贪心。很多初学者会误以为“每次选择能跳得最远的那个位置”这其实是错的。我见过有人拿[2, 3, 1, 1, 4]举例从 0 开始第一步如果贪心跳最远到下标 2再跳只能到下标 3最后还要一步到下标 4总共 3 步但最优解是先从 0 跳到下标 1再直接跳到末尾只需要 2 步。所以“能跳最远”不等于“这一步走得最远”。正确的贪心策略是在当前位置能覆盖的范围内先不要急着跳而是遍历这个范围内所有位置记录“从这些位置再跳一次能到达的最远位置”。当你走到当前覆盖范围的边界时不得不跳一次这时再跳并把下一段覆盖范围更新成刚才记录的最远位置。这样每一步都让下一次的覆盖范围最大化跳跃次数自然最少。4.2 区间覆盖式的贪心证明为什么这个策略是对的我们可以用数学归纳法来想。假设当前已经跳了 k 步能覆盖的范围是 ([0, end])。在这个范围内任意位置 j 都是可达的。对于任意 j从 j 出发一步能到达的最远位置是 (j nums[j])。我们选择在到达 end 时跳跃并且下一次起点一定落在 ([0, end]) 内而这一步能到达的最远距离就是[ \max_{0 \le j \le end} (j nums[j]) ]这个最大值其实就是下一次跳跃后的覆盖范围右端点。如果存在一种 k1 步的方案能覆盖更远那一定是因为它从某个 j 出发达到了更远的位置但我们的 max 已经把范围内所有 j 都考虑到了所以不存在比这个更远的 k1 步方案。每一步都取到理论最大值最终总步数就是最小的。这个证明思路其实也带着“贪心选择性质”的味道局部最远覆盖全局最优步数。它和相邻交换法的区别在于相邻交换法证明的是“两个元素谁先谁后”而区间覆盖贪心证明的是“每一步的覆盖范围可以取到上界”。4.3 Python 代码与边界测试跳跃游戏2的标准写法可以省掉 DP只用一次遍历。下面是我实际在用的版本def jump(nums): n len(nums) if n 1: return 0 max_pos 0 # 当前这一步能够到达的最远位置 end 0 # 当前这一步的覆盖边界 steps 0 # 已经跳的次数 for i in range(n - 1): # 遍历当前位置能覆盖的区间更新下一步能到的最远位置 max_pos max(max_pos, i nums[i]) # 走到了当前覆盖范围的边界必须再跳一次 if i end: steps 1 end max_pos if end n - 1: break return steps有几个边界值得注意。第一n 1时直接返回 0因为已经在终点。第二循环只走到n - 2不需要遍历最后一个位置因为到了终点就不需要再跳了。第三end n - 1提前退出能省下不必要遍历。题目保证一定能到达终点所以不需要额外判断失败但如果是自己写测试可以加一个防御性检查。如果你把[2, 3, 1, 1, 4]丢进去运行结果是 2。过程是从下标 0覆盖范围 [0, 0]遍历到 index 0 时max_pos 2遇到边界i endsteps1end2。然后遍历 index 1 时max_pos max(2, 13) 4index 2 时max_pos max(4, 21) 4当i endi2时steps2end4已经到达末尾返回 2。4.4 面试现场怎么把两道题串起来讲如果你在面试中被问到跳跃游戏2很多人的第一反应是往 DP 上想。确实dp[i] min(dp[j] 1)也能做但复杂度是 O(n^2)遇到大数据就挂了。面试官更想听到的其实是你能识别出这是“区间覆盖贪心”而不是“排序贪心”。我建议的讲解节奏是先说明这个题不能排序因为数组顺序固定再用“最小跳跃次数”转化为“每步扩展覆盖区间”最后写代码。如果面试官追问怎么证明就用上面那个“上界”论证。反过来如果面试官先问“排队接水”这类题你就可以引出相邻交换法然后对比说“跳跃游戏2 是另一种贪心核心不是交换顺序而是每一步覆盖范围最大化”。这样既展示了你对不同贪心模型的区分能力也让整个回答更有层次。5. 踩坑记录与常见问题排查5.1 为什么交换相邻两项能推出全局最优最容易被问懵的点很多初学者用相邻交换法时心里一直有个疑问我只证明了“相邻交换不会让结果变差”但凭什么说最终排序就是全局最优答案藏在“任意排列都可以通过有限次相邻交换变成目标排列”这件事里。假设你推导出比较规则 R并且 R 满足严格弱序那么对任何一个不是按 R 排序的排列一定存在至少一对相邻元素违反了 R 的顺序。交换这一对相邻元素目标函数不会变差。反复进行这样的交换最终你会得到一个按 R 排序的排列而且每一步都不会让目标函数变差。也就是说排序后的结果至少不比任何一个初始排列差所以它就是全局最优。这个论证里最容易翻车的地方是比较规则 R 必须满足严格弱序。如果 R 不满足传递性那“反复交换直到有序”的过程可能永远不会收敛或者收敛到某个局部最优但全局不是最优。所以用相邻交换法最后一定要花 30 秒确认传递性。5.2 相邻交换法失效的典型场景不是所有“顺序可变求极值”都适合相邻交换法。我总结过三类失效场景。第一目标函数不只是相邻两项的代价还依赖全局状态。比如某些调度问题后面任务的等待时间不仅取决于前一个任务还取决于所有已完成任务的总耗时。这种情况下相邻两项交换时后面所有任务的代价都会变不能只比较两个元素。第二题目对排列有额外约束比如要求某些任务必须在某些任务之前或者有资源上限单纯排序解决不了需要 DP 或搜索。第三比较规则不满足传递性。这个刚才说过一旦出现循环比较排序直接失效。我之前做一个带截止日期的任务调度问题用相邻交换法推出“按截止时间排序”结果提交 WA。后来发现题里还要求如果任务超时罚款是阶梯式增长不是线性增长这会导致交换后对后续任务的影响无法忽略。这时候正确的解法是贪心优先队列而不是纯排序。5.3 调试用的数据生成器和暴力对拍遇到排序策略不确定的题我强烈建议写一个数据生成器加暴力对拍脚本。做法也很简单随机生成长度在 1 到 8 之间的测试数据用permutations枚举所有排列算出精确答案再和你排序后的结果对比。关键点是生成数据时不要只生成“均匀随机”的整数要覆盖边界情况。比如任务罚款问题让某些cost和penalty相同让某些cost为 0如果题目允许让某些值特别大、特别小。这些边界最容易让浮点比较或者溢出问题现出原形。如果暴力对拍挂了不要急着改贪心规则。先把挂掉的那组数据打出来手工跑一遍相邻交换推导看看是不是漏了什么项。很多时候问题出在目标函数定义上比如你算代价时少算了“当前时间”这一项。所以对拍脚本里暴力函数和贪心函数必须用同一个代价公式否则就是拿着两把不一样的尺子量东西。5.4 几个容易忽略的实现细节先说比较器。Python 的sort默认只接受key函数如果你要用自定义比较器需要functools.cmp_to_key。但cmp_to_key的返回值要让cmp(a, b)返回负数表示a b这个方向特别容易搞反。我每次写完都会先用三个元素的手工用例验一下排序结果确认方向对了再提交。再说整数溢出和精度。只要是比值排序一律用交叉相乘不要用浮点除法。C 里要注意乘积可能超过 int 范围开long longPython 虽然没有溢出问题但浮点除法依然可能因为精度问题造成排序不稳定。我之前测试过一组cost10^9, penalty1和cost1, penalty10^9的数据用浮点除法在极端情况下结果会错。还有一个细节是“相等元素怎么处理”。相邻交换法推导出的规则往往只给出严格小于关系如果两个元素相等谁前谁后其实无所谓。但你要确保比较器对相等元素返回 0不然 C 的std::sort可能触发未定义行为Python 的cmp_to_key则可能效率变差。最稳妥的做法是推导出严格比较规则后在比较器里把相等情况显式返回 0。我在实际刷题中养成了一个习惯凡是遇到“顺序可变、求极值”的题先试着用相邻交换法推两个元素的交换条件推得出来并且满足传递性就大胆写排序推不出来再往 DP、贪心优先队列这些方向考虑。这个判断过程可能只要几分钟却能在后面省下大量 debug 时间。跳跃游戏2这种“顺序固定”的贪心题我也会用类似思路去想想每一步的局部最优能不能达到全局上界能就用不能就找反例。说到底贪心不是靠猜而是靠“局部调整不劣”或者“覆盖范围上界可达”这类理由把每一步的选择钉死。希望这篇算法日记能让你少走一些我走过的弯路。
