今天是我更弱智的算法学习系列的第23天。这个名字不是自暴自弃而是我自己总结出来的一套学习策略把自己当成一个什么都不懂、只会用最笨办法的人先把一个算法用最朴素的方式跑通再去理解它背后的道理。今天这个位置刚好轮到算法学习路上绕不开的贪心算法。如果你在网上搜算法相关内容大概率会看到贪心算法这个关键词和动态规划剪枝算法KMP一起出现在推荐列表里。这篇博文就记录我第23天的完整学习过程从翻车到理解顺便帮同样被贪心搞晕的人少走几条弯路。1. Day 23 的开场白为什么我管贪心叫弱智算法1.1 一道硬币找零题让我当场翻车我一开始以为贪心就是每一步选最好。于是打开一道硬币找零题。假设硬币面值只有1、3、4要凑出6。我的第一反应是先选4还差2再选1还差1再选1。结果用了3枚硬币。但人肉看一眼就知道正确答案是33只要2枚。当场翻车。这说明每一步选最好在有些情况下根本不成立问题出在这一步选得最好后面就没得选。这个例子我后来一直记着它帮我区分了贪心和感觉的区别。如果你觉得自己已经理解贪心算法不妨先拿这个例子考一下自己。它虽然简单却浓缩了贪心最容易犯错的地方局部最优并不自动等于全局最优。1.2 贪心到底是什么不是闭眼乱选贪心的正规说法是在每一步决策时只考虑当前状态下的局部最优选择并期望这些局部最优能叠加成全局最优。期望两个字是重点。很多初学者把贪心理解为闭眼乱选其实贪心是对选择规则有严格要求的算法只是它不做回溯不重新考虑之前的决定。用生活例子类比找工作。手头有一批Offer贪心策略就是选当下薪水最高的签完不回头。这个策略在某些市场里是合理的但如果后续出现一个成长性更好或期权价值更高的公司贪心就会错过。算法题里的道理一模一样你以为你选的是全局最优其实只看到了当前这一步。1.3 今天这篇适合谁读如果你刚开始学算法被贪心算法动态规划回溯这些术语吓到这篇适合你。如果你已经刷了一段时间题但拿到一个陌生题目还是不知道该不该贪心这篇也适合。我假设你已经会写基本的循环和数组但完全没接触过贪心也没关系跟着例子走就能理解。我还会尽量少用复杂的数学证明多讲直觉、反例、代码把贪心从玄学变成可以按步骤执行的判断方法。当然如果你已经能熟练证明贪心正确性可以直接跳到第4章看总结。2. 贪心成立的底层逻辑局部最优怎么变成全局最优2.1 找零钱为什么是反面教材还是回到硬币面值[1,3,4]、目标金额6的例子。贪心选择过程是第一次选最大的4剩余2第二次只能选1剩余1第三次再选1结束。硬币数3。最优方案是选3剩余3再选3结束。硬币数2。为什么贪心失败因为在面值1、3、4之间不存在一种谁大谁就绝对划算的结构。4虽然单个面值大但它和3的组合相比占用了太多凑数空间。换句话说局部最优选最大面值没有保持剩余子问题的最优性。一个面值体系如果可以贪心通常要求满足某种倍数关系比如1、5、10、25每个大面值都能被小面值凑出来这样大面值不会浪费组合可能。所以学贪心第一步不是背模板而是理解为什么有些选择看起来贪心实际坑。2.2 活动选择问题贪心正确性的完整证明活动选择问题是贪心最经典的正面教材。设有一组活动每个有开始时间s[i]和结束时间f[i]选择最多数量的互不重叠活动。贪心规则按结束时间从小到大排序然后依次选择第一个与已选活动兼容的活动。我来说服自己为什么这一定最优设最优解中第一个被选的活动是k而贪心选择的是m。因为m在排序后出现最早所以m的结束时间不大于k的结束时间。把最优解里的k换成m。由于m结束得不比k晚所以原本排在k后面的所有活动和m依然是兼容的。换完之后的活动集合数量和原来一样多。重复这个替换过程最后得到的最优解就是从贪心第一步开始的最优解。因此贪心策略不会让结果变差。这就是交换论证的思想。用生活类比你在大厅排队参加各种短会议碰到的第一个结束的会议一定可以安全接上其它任意会议所以先选它不亏。2.3 区间问题里的贪心套路学会活动选择之后很多区间题都从这个模型变形而来。常见的包括无重叠区间按结束时间排序能选就选最后用总数减能选数量。用最少数量的箭引爆气球把气球看作区间排序后尽可能用同一点覆盖更多区间。合并区间这个通常按开始时间排序然后扫描合并。注意一个关键区别活动选择和无重叠区间这类求最大不重叠数量的问题按结束时间排序合并区间这类求并集问题按开始时间排序。原因在于你想优化的是数量还是连续性前者希望每个选择留出最多剩余空间后者希望抓住所有可能重叠范围的起点。问题类型排序维度贪心策略最大不重叠活动数结束时间每次选最早结束最小箭引爆气球结束时间尽量往最右射合并重叠区间开始时间维护当前覆盖范围3. 实战三道题把贪心从感觉变直觉3.1 分发饼干排序后双指针的教科书操作题目每个孩子有一个胃口值g[i]每个饼干有一个尺寸s[j]。每个孩子最多给一块饼干且饼干尺寸大于等于胃口才能满足。求最多能满足几个孩子。直觉小饼干给小胃口大饼干留着给大胃口因为大饼干能覆盖的需求范围更大。做法两个数组都排序用两个指针从最小的胃口和最小的饼干开始匹配。如果当前饼干能满足当前孩子指针都前进答案加一如果不能说明这块饼干太小饼干指针前进换一块更大的。def findContentChildren(g, s): g.sort() s.sort() i j 0 while i len(g) and j len(s): if s[j] g[i]: i 1 j 1 return i这道题骗过很多人的地方在于你可能会贪心地用最小饼干去满足最大胃口结果发现小胃口没被利用答案反而变小。排序之后按最小满足当前最小是对的因为饼干分配顺序不影响可行性但影响匹配数量。时间复杂度是排序主导的O(nlogn)空间复杂度O(1)。3.2 加油站净消耗与总油量的关系题目变成环形路线每个加油站的油量gas[i]从加油站i开到i1需要消耗cost[i]。问从哪个站出发能绕一圈回来如果不存在就返回-1。第一次看到这题我想的是模拟每个起点复杂度O(n^2)。后来发现一个漂亮的贪心思路。先算每个站的净收益diff[i] gas[i] - cost[i]。如果总收益total小于0说明整个环的油不够无论如何都走不完直接返回-1。如果总收益大于等于0那么一定存在一个可行起点。怎么找从左到右遍历用cur记录从当前起点出发跑到现在的剩余油量。一旦cur小于0说明从当前起点到当前位置这一段没跑通。关键结论这一段中的任何位置都不能作为全局起点。于是把起点暂定为i1cur清零继续往后试。遍历完的start就是答案。为什么中间任何位置都不能当起点因为你的cur是从start开始一路累加的结果如果cur在i处变成负数说明从start出发到i的每段净收益叠加在start点上是无法支撑到i的。如果从start和i之间的某个k点出发相当于把前面这段的负收益丢掉了但你丢失了从start到k可能积累的正收益所以在i点依然会失败。这个前缀亏空是累积的不能靠换起点躲过。def canCompleteCircuit(gas, cost): total 0 cur 0 start 0 for i in range(len(gas)): diff gas[i] - cost[i] total diff cur diff if cur 0: start i 1 cur 0 return start if total 0 else -1注意不能在循环中间因为cur小于0直接返回-1因为后面的总油量还没累计完total可能被后面补回来。3.3 跳跃游戏从右往左的最远距离跳跃游戏的描述数组nums每个元素代表你在该位置最多能跳多远初始在下标0问能否到达最后一个下标。这个题和动态规划、回溯都有关但一个简单贪心就能解决维护一个变量max_reach表示当前能到达的最远位置。遍历每个位置i如果i已经大于max_reach说明这个位置根本不可达直接返回False。否则更新max_reach max(max_reach, i nums[i])。一旦max_reach大于等于n-1可以提前返回True。为什么一次遍历就能判断因为max_reach记录的是所有已访问位置中能延伸的最大右边界。在这个边界内每个位置都是可达的边界外的位置如果想可达必须依赖某次跳跃把它覆盖进边界里。如果遍历到某个i时i max_reach说明没有任何已访问位置能跳到i更不可能跳到后面。def canJump(nums): n len(nums) max_reach 0 for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return False这是一个正着贪的题和前面的活动选择一样贪心的核心在于维护一个单调扩大的可达范围。它能成立是因为跳跃能力具有传递性如果a能跳到bb能跳到c则a一定能通过b跳到c。这种传递性保证了局部选择不会污染全局状态。4. 判断贪心可用性的四步法我的排雷清单4.1 子问题独立吗贪心最怕的情况是这一步的选择会改变后面所有选择的条件。如果选择完当前项后解决剩余问题的场景和原问题结构完全一样只是规模缩小贪心才有戏。活动选择是典型的独立子问题选完最早结束的活动后剩下的问题就是在更晚的时间窗口里继续选活动。而硬币找零的反例里选4后剩余问题变成了用1来填补2这个子问题和你有没有选3密切相关两个子问题不是独立的。看到一个新题先问自己我做出第一步选择后剩下的还是一个同构问题吗4.2 局部最优能传导到下一步吗更直白地问这一步选了最优下一步的最优还能利用这个选择吗如果不能那这一步的最优就是假最优。拿爬山来类比只看眼前最陡的坡往上爬可能爬到一个小山包四周都是悬崖想再往上就得先下山。算法里的下山重来意味着要推翻之前的决策贪心不允许这么干。所以只有每一步都不会把路堵死的选择才能贪心。比如分发饼干里用最小饼干满足最小胃口这一步不会堵死大饼干的去路反而把大饼干释放给了大胃口。4.3 能不能构造一个反例这是我在刷题时最常用的排雷手段。正式写代码前先拿一个很小的测试用例手算一遍贪心再努力构造一个让它失败的用例。如果能构造出来说明题目大概率不是贪心需要退回考虑动态规划、回溯、双指针等其它思路。比如0-1背包问题表面上是按单位重量价值从高到低装但如果不允许拿部分物品贪心会失败。构造一个容量10物品A重量6价值6单位价值1物品B重量5价值4单位价值0.8物品C重量5价值4单位价值0.8。贪心先选A剩余容量4装不下B或C总价值6最优是BC总价值8。反例一秒钟就找到了。4.4 与动态规划做一次同题对比如果经历前三步后你还是拿不准可以做一个对比这题的暴力解法是不是会大量重复计算子问题如果是它可能更适合动态规划。而贪心只是动态规划的一个特例每一步的状态转移被固定为最优选择不需要枚举所有转移。我用一个表格记录自己常用的判断维度维度贪心算法动态规划决策方式当前最优选完不回头枚举所有可能保留最优历史子问题关系强独立可替换重叠子问题时间复杂度排序扫描通常O(n log n)状态数乘转移复杂度通常O(n^2)正确性来源需证明贪心选择性质状态转移方程保证代码难度往往很短往往需要数组或记忆化在实际刷题中如果题目里出现最多最少最大数量这类词我会把贪心、DP、二分、排序都放进候选然后先用反例法把明显不行的排除掉。贪心不是万能的但它确实是最快能验证的一类思路。5. 贪心题目的代码骨架与三个常见坑5.1 一套够用的代码模板剥掉各种奇奇怪怪的题目背景很多贪心题就是排序 扫描 状态维护。我总结了一套模板可以覆盖大部分区间类、配对类贪心def greedy_template(items): # 1. 排序选对排序维度 items.sort(keylambda x: x[1]) # 比如按结束时间 ans 0 current None # 2. 扫描边扫边做决策 for item in items: if acceptable(current, item): ans 1 current item return ans这只是骨架实际题目的acceptable逻辑差别很大。但骨架能提醒你贪心的代码往往很短真正的难度在排序维度和条件判断上。5.2 三个debug到崩溃的常见坑先说我踩过最多的坑排序key选错。区间类题目按左端点排序还是右端点排序直接影响正确性。我只能用经验判断如果目标是数量最大化优先按结束时间排序如果目标是覆盖或合并所有范围优先按开始时间排序。两者混用会在示例通过、提交失败的边缘反复横跳。第二个坑是状态更新顺序。比如跳跃游戏里必须先把是否可达判断了再更新max_reach。如果先更新max_reach再判断i max_reach会让本来不可达的位置被未来能力覆盖导致错误判断。这也是很多贪心题目的通病当前步只能使用截止到当前的信息不能看到未来。第三个坑是边界条件。加油站题里如果循环里cur小于0就立即把start设为i1不要等循环结束但total一定要在整个循环结束后判断。有些新手会在cur小于0时直接返回-1这是错的因为当前片段亏空不代表整个环路油不够。贪心题代码越短越要抠边界。提示如果一次提交没通过不要急着改排序方向先构造一个反例手算一遍。用纸笔推演比在编译器里瞎试快得多。5.3 时间复杂度和优化空间绝大多数贪心题的时间复杂度由排序主导也就是O(n log n)。如果题目输入已经有序可以做到O(n)。空间复杂度一般是O(1)或O(n)取决于是否需要额外数组存diff、区间等。和动态规划相比贪心最显著的优势是快、省空间。这也是面试官喜欢先问贪心的原因——如果能贪心就不需要上DP那样重的武器。6. 学完这一天我对弱智和算法的重新认识6.1 所谓弱智其实是把复杂度留给思考学完贪心这一天我最大的感受是一个看起来弱智的算法恰恰是最需要动脑证明的算法。每一步选当前最优听起来像不动脑子但真正难的是判断当前最优能不能通向全局最优。这个判断不是靠背模板而是靠问自己四个问题子问题独立吗局部最优能传导吗能构造反例吗和DP比更合适吗这四个问题才是贪心的灵魂。6.2 下一步该学什么如果你也在按这个顺序学算法我建议学完贪心后立刻去对比动态规划。尤其推荐0-1背包最长上升子序列这类能同时用贪心和DP视角看的题你会更快形成判断力。之后可以按热词里经常出现的顺序继续推进剪枝算法回溯优化、KMP字符串匹配、归并排序分治基础、A*启发式搜索。贪心是这些算法里最简单也最容易误用的一块把它真正吃透后面学DP会顺畅很多。6.3 学习贪心时我私藏的资料最后分享几个我实际用过的资料不吹不黑LeetCode的贪心标签题单按通过率排序刷前20道即可。《算法导论》第16章贪心算法与拟阵学有余力再看拟阵部分。B站搜贪心算法 正确性证明找有画图讲解的视频。自己准备一个反例笔记本把能推翻贪心的小用例记下来比如[1,3,4]凑6、0-1背包的容量例子。面试前翻这个本子比重新刷题管用得多。第23天的贪心之旅到这里就结束了。明天我打算用同样的弱智方式去啃一啃动态规划看看这两个经常一起出现的算法到底在哪些题上会打起来。