算法与数据结构 - 贪心篇

简述

贪心问题和二分法一定程度上非常相似,属于非常直观的算法。

简单题甚至不用思考,怎么做一目了然。而困难题除非曾经做过相似题,或者灵光乍现,不然很难解,甚至根本想不到可以用贪心做。

贪心的本质是选择每一阶段的局部最优,从而达到全局最优。与其说贪心是一种算法倒不如说是一种思想。

贪心算法的难点

1. 什么时候贪?
• 哪些题可以用贪心做, 哪些题不可以?
2. 怎么贪
• 如何获得全局最优?如何获得局部最优?

什么时候贪?

不同于之前总结的题型和技巧,贪心算法真的没有统一的套路,更没有类似回溯的模板代码。

例如

• 有一堆钞票,你可以拿走十张,如果想达到最大的金额,该怎么拿?



指定每次拿最大的,最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。

反例

• 如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了。这时候就需要动态规划。

因此,当拿到一道算法题,想要知道可不可以用贪心算法的时候,需要思考一下三个点。

1. 题目是否是求极值(求解最优)



贪心算法一定求极值,譬如最大、最小值,最少步、最多收益等。通常看到求极值算法,非动(DP)即贪(Greedy)。

这么说有点武断,但反过来说,如果题目不是求极值,那么一定用不上贪心算法,则非常可靠。

2. 题目是否一眼能看出来其他解法(题型显著性)



譬如,棋盘类算法明显是回溯、有效括号明显是栈、二叉树的搜索明显是dfs。

如果根据做题经验,能够一眼看出题型暗示的最优、最有效的解法,那么可以果断放弃贪心。

3. 全局最优与局部最优明显冲突(违背贪心核心思想)



从题干,或者题目给的test case中,能够找出,或者能够发现反例,证明全局最优无法从局部最优获取,那么就违背了贪心的原则,继续思考贪心将没有任何意义。

譬如,背包问题中,无论怎么选择贪心策略,都能举出反例。又或者是Travelling Salesman Problem等NP hard问题,这种问题规模特别大,或者存在复杂约束条件,导致没办法拆解成可以解的子问题,因此根本无法使用贪心算法有效求解。

怎么贪?

首先明确一点:贪心没有套路,说白了就是常识性推导加上举反例。

原则一

• 贪心思路往往很巧妙,并不简单。

原则二

• 贪心无套路,也没有框架之类的,需要多看多练培养感觉才能想到贪心的思路。

刷题经验总结

直观贪心问题

特点:

• 这类题目普遍是简单题,会给人一种贪心算法很简单的错觉,因为贪心有时候接近于常识,或者题目本身比较生活化,符合人们日常的逻辑。

编号	名称	难度	贪心策略
455	分发饼干	简单	全局:喂饱尽可能多的小孩。 局部:大饼干优先喂给胃口大的 / 小饼干优先喂给胃口小的
860	柠檬水找零	简单	全局:完成全部账单的找零。 局部:遇到账单20,优先消耗美元10,完成本次找零。

极值/峰值问题

特点:

• 这类题型大多为中等难度,会让初学算法的人开始逐渐意识到贪心算法的难度。
• 这类题目对于学习了比较完整的算法技术栈,但还没有完全熟练掌握的人来说更容易出现误区(但只是针对贪心而言)。因为极值、峰值问题,可能第一反应是用动态规划做(其中很多用DP也确实是可以做的,但肯定是贪心效率高)。
• 中等难度的题,往往动态规划的递推关系不难发现,而相比之下贪心策略则并不直观。面试中还是应该功利一点,想出来哪个用哪个。尽管贪心往往在时间复杂度上更有优势,但动态规划的算法还是更能证明面试者的水平。

编号	名称	难度	贪心策略
376	摆动序列	中等	全局:整个序列有最多的局部峰值。 局部:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值。
53	最大子序和	中等	全局:选取最大“连续和” 局部:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。
122	买卖股票的最佳时机 II	中等	这题可以用动态规划做,但贪心更优。 技巧:理解利润拆分是关键点。把整体利润拆为每天的利润,就很容易想到贪心了。 全局:得到最大利润。 局部:只收集每天的正利润。
1005	K次取反后的最大数组和	简单	贪心思路比较直观:两次贪心。 第一次:先解决负数(贪心增长) 全局:整个数组和达到最大。 局部:让绝对值大的负数变为正数,当前数值达到最大。 第二次:全是正数(贪心亏损) 全局:同上。 局部:只找数值最小的正整数取反,这样亏损最少,当剩余k为偶数时甚至不亏,当前数值可以达到最大。

约束条件下移动问题

特点:

• 这类问题大多数难度为中等,也有少量简单和困难题,但这两个难度的移动问题通常不具有贪心代表性。
• 移动问题本身有种暗示使用指针的感觉,因此贪心思想往往是针对约束条件的,譬如移动的损耗、移动耗油、移动的最远距离等。

编号	名称	难度	贪心策略
55	跳跃游戏	中等	技巧:看覆盖范围,覆盖范围内一定是可以跳过来的,不用管是怎么跳的。 那么问题就转化为跳跃覆盖范围可不可以覆盖到终点! 全局:最后得到整体最大覆盖范围,看是否能到终点。 局部:移动下标每次取最大跳跃步数(取最大覆盖范围)。
45	跳跃游戏II	中等	技巧:以最小的步数增加最大的覆盖范围,直到覆盖范围覆盖了终点 全局:达到终点,步数最少。 局部:求当前这步的最大覆盖,那么尽可能多走,到达覆盖范围的终点
134	加油站	中等	误区:乍一看是模拟题,但是最直观的模拟思路并不是贪心的做法。 技巧:每个加油站的补充和损耗相减,定义净增长。当从0跑到index为i的加油站,发现累积净增长为负数,则说明0-i之间不存在可以跑完全程的出发点,从i+1继续尝试。 全局:找到可以跑一圈的起始位置。 局部:累积净增长为负,局部非最优,一定不是全局最优。

区间重叠问题

特点:

• 这类问题的难度基本集中在中等。也是少有的比较有套路的贪心算法题。
• 这种题目的核心是可以将问题转换求解区间的重叠部分,需要谨慎辨别。而求解区间重叠问题的关键技巧就是要选定一个方向(左边界/右边界)对数组进行排序,从而让区间尽可能地重叠。
• 排序后只需要关注重叠区间的右边是否能够超过新区间右边界就行。在此基础上就可以对重叠和不重叠的情况下分别作出对应处理,从而解决不同的问题。

编号	名称	难度	贪心策略
452	用最少数量的箭引爆气球	中等	技巧:排序,让可能重叠的气球凑到一起。 全局:把所有气球射爆所用弓箭最少。 局部:当气球出现重叠,一起射,所用弓箭最
435	无重叠区间	中等	技巧:排序,让区间尽可能的重叠 全局:让所有区间不重叠 局部:当两个区间重叠时,舍弃右边界(从左往右遍历)更远的区间。
763	划分字母区间	中等	技巧:统计每个字符出现的最远index。 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,说明找到分割点。 【其实是模拟法,但是有点贪心的意思】
56	合并区间	中等	技巧:和452/435一样,只不过结果呈现不同

多维度约束贪心问题

特点:

• 这类问题大多数是困难题和较难的中等题。因为需要考虑至少两个维度的情况(一般最多也就是两个维度)。
• 这类问题有个共同的技巧:

先考虑哪一边都可以! 就别两边一起考虑,那样就把自己陷进去了。

编号	名称	难度	贪心策略
135	分发糖果	困难	维度一:从左往右遍历 全局:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果 局部:只要右边评分比左边大,右边的孩子就多一个糖果。 维度二:从右往左遍历 全局:相邻的孩子中,评分高的孩子获得更多的糖果。 局部:只要左边评分比右边大,左边的孩子就多一个糖果,同一个小孩,分到的糖果取维度一和维度二中的较大值。
406	根据身高重建队列	中等	技巧:先从大到小按照h排个序,再来贪心k 因为先排序k会发现两个维度都没确定下来。 全局:最后都做完插入操作,整个队列满足题目队列属性。 局部:优先按身高高的people的k来插入。插入操作过后的people满足队列属性

意想不到贪心问题

特点:

• 这类问题一般出现于中等和困难题。这种问题对贪心的暗示不强,甚至出题者可能会刻意误导。但是在求极值的时候会发现,求极值思路符合贪心思想。
• 通常这种题在处理的过程中,设计和实施贪心算法有较高难度,也往往正是因为没办法在第一时间构思出足以说服自己的贪心框架,导致错失贪心的解法。

编号	名称	难度	贪心策略
738	单调递增的数字	中等	误区: 单纯看题以为是暴力破解,但铁timeout,因此不得不从贪心出发。 技巧:从后往前遍历数字时,遇到非单调递增情,前数退位,后数可以直接为9 【坑:所有后数都要为9,否则无法处理1000000的情况】 全局:最终数字是小于原数字的最大单调递增数字。 局部:使得当前相邻两位数满足单调递增。
968	监控二叉树	困难	尽管是二叉树,但是摄像头放置的最小数量还是遵从贪心思路。 技巧:发现叶子节点的父节点,和根节点的子节点放摄像头最划算。但只能从一头开始遍历,相比之下,从叶子节点开始遍历更划算(指数级增长),因此DFS选择后序搜索。 全局:全部摄像头数量所用最少 局部:让叶子节点的父节点安摄像头,所用摄像头最少。 难点:想到通过dfs传参的方式,进行父节点摄像头覆盖状态的流转。

参考资料

• 代码随想录: 贪心算法理论基础
• 代码随想录: 贪心一般解题步骤
• 代码随想录: 贪心算法总结篇
• Leetcode: 面试经典150题
• Leetcode: 尊享面试100题
• Leetcode算法