1 贪心算法
❝
「贪心算法」（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
❞
❝
什么好我要什么，最大、最小、最多，这就是贪心。
❞
通常贪心算法的代码会非常短(比如下图的代码)而且思路也非常的简单，但贪心算法真正的难点在于确定我们当前的问题确实可以使用贪心算法。
var eraseOverlapIntervals = function(intervals) { if(intervals.length == 0) return 0 intervals.sort((a,b)=>a[1]-b[1]) let i = 1, pre = 0, res = 0 let len = intervals.length while(i < len){ if(intervals[pre][1] <= intervals[i][0]){ pre = i res++ } i++ } return len - res};
这道题是LeetCode中第235题，无重叠区间, 本文从分析这道题来一起学习贪心算法。
2.典型问题求解
还是分析我们上面提到的问题。
题目意思：题目的意思是给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
换一种思路，如果我们找到了一种方法，获得所有不重叠的区间，通过全部区间集合的数量减去最长的不重叠的区间的数量，那么就可以知道需要移除区间的最小数量。「本题上面提供的解法中正是通过这种思路来实现的代码。」
就比如 [[1,2], [2,3], [3,4], [2,4]] 这个区间里面，我们能的到的最长的不重复区间是 [[1,2], [2,3], [3,4]] , 如果我们能得到这个最长的不重复子区间，那么自然我们就能知道原问题中需要移除区间的最小数量就是 1.
然后我们现在的问题就转到了如何「获得最长的不重叠子区间」，
思路
我们按照区间前后的思路去思考这么一个问题
首先我们分析这么一个情况，如果在区间集合里面有这么两个区间：[2,3] 和 [2,4] ,让我们选择一个区间，能够让我们在当前情况下能够得到更多的不重叠区间，因为*[2,3]* 的 结尾是3小于4，也就意味着从前往后的思路中，我们如果拿 [2,3] 这个区间就能比拿 [2,4] 更有可能获得更多的区间。比如正好有一个 [3,4] 这个区间，那我们就能百无禁忌的收入整个集合中。
也就是说，结尾越小，留给后面的空间也就越大，后面也就越有可能容纳更多的区间。（其实利用现实中的现象也很容易理解，比如我们要给一个罐子里装大小不一的糖果，要求我们装最多的糖果，那我们在每一次选择糖果的时候，都选择当前情况下选择完后能够让剩余空间最大的糖果。更好的例子请在评论区打出）
整体思路：按照区间的结尾顺序，每次选择结尾最早的，且和前一个区间不重叠的区间。
接着我们逐行分析代码：
var eraseOverlapIntervals = function(intervals) { // 如果接收到的数组是空数组，那么直接返回0就行了~ if(intervals.length == 0) return 0 // 贪心算法很多都涉及到排序，这里我们根据区间的末尾按顺序排序 intervals.sort((a,b)=>a[1]-b[1]) // i 保存遍历当前值下标， pre 表示上一个遍历值的下标， res表示不重复区间的长度 let i = 1, pre = 0, res = 0 // 获取长度，这里其实是一个优化小点，这里获取后下面每次都直解拿值，会比通过引用拿属性值快一些 let len = intervals.length // 遍历所有的子区间 while(i < len){ // 在当前子区间的开始比上一个子区间的末尾相等或者大的时候 // 那么不重复区间就可以包括这个区间，否则就跳过这个区间（让i++） // 上一个区间依然是原有的上一个区间。 // 比如[2,3],[2,4],[3,4], 因为区间[2,4]开始的2比上一个区间的3大， // 那么就会跳过这个区间，然后这个区间也不加入到不重叠子区间中 if(intervals[pre][1] <= intervals[i][0]){ pre = i res++ } i++ } // 返回值就是原先区间集合的长度减去不重复子区间的长度 return len - res};
End
当然，贪心算法有些时候也会非常难，不是简单的每次去一个最大值或者最小值就能完成任务，有些时候在完成一个大问题的时候，就其中的某一小步需要用到贪心算法。
通常在面试中，一般都会糅合贪心算法思想和其他领域的问题来形成一个更大的问题来考察面试者。
无「bug」! 不码农! 我们下期再见！
点击咨询 