&emsp;&emsp;贪心算法（Greedy Algorithm）会在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，不能回退，从而希望结果是最好或最优的算法。它是动态规划的一种特例，需要满足更多的限制条件。 &emsp;&emsp;贪心算法在有最优子结构的问题中尤为有效（例如求图的最小生成树、哈夫曼编码等），最优子结构是指局部最优解能决定全局最优解。即问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 ## 一、区间调度 &emsp;&emsp;给定多个 \[start, end\] 的区间集合，算出有多少个不重叠的区间。例如 \[1,3\], \[2,4\], \[3,6\]，有两个不重叠的区间 \[1,3\], \[3,6\]，因为边界相互接触，并不算重叠。例题：[435\. 无重叠区间](https://leetcode-cn.com/problems/non-overlapping-intervals/)。 &emsp;&emsp;解题思路如下所列： &emsp;&emsp;（1）根据终点对区间进行排列。 &emsp;&emsp;（2）从区间集合中选取一个终点最小的区间 \[start, minEnd\]。 &emsp;&emsp;（3）将所有与 \[start, minEnd\] 相交的区间从集合中移除。 &emsp;&emsp;（4）重复执行（2）和（3），直至遍历完集合。 &emsp;&emsp;具体实现代码[如下所示](https://codepen.io/strick/pen/mdVYrRd)。 ~~~ function eraseOverlapIntervals(intervals) { intervals.sort((a, b) => a[1] - b[1]); let curEnd = intervals[0], //终点最小的区间 count = 1; //不重叠的区间数 intervals.forEach((value) => { if (value[0] < curEnd[1]) { //过滤起点比curEnd终点小的区间 return; } count++; curEnd = value; }); return count; } ~~~ ## 二、分糖果 &emsp;&emsp;假设有 m 块糖果和 n 个小孩，但是 m > n，即糖果少，小孩多，会有一部分小孩分不到糖果。 &emsp;&emsp;每块糖果的大小不等，这 m 个糖果的大小分别是s1，s2，s3，……，sm。每个小孩最多分到一块糖果，并且每个小孩对糖果大小的需求也不同，他们的需求分别是g1，g2，g3，……，gn。 &emsp;&emsp;如果 sj >= gi ，那么可以将这个饼干 j 分配给小孩 i ，这个小孩会得到满足。该如何分配糖果，才能满足最多数量的小孩。例题：[455\. 分发饼干](https://leetcode-cn.com/problems/assign-cookies/)。 &emsp;&emsp;解题思路是每次从剩下的小孩中，找出对糖果需求最小的，然后发给他当前糖果中能满足他的最小糖果，[如下所示](https://codepen.io/strick/pen/bGEyBYK)。 ~~~ function findContentChildren(g, s) { g.sort((a, b) => a - b); //升序排列 s.sort((a, b) => a - b); //升序排列 let n = 0, m = 0, count = 0; //满足的小孩人数 while (n < g.length && m < s.length) { if (g[n] <= s[m]) { //小孩能够得到满足 n++; m++; count++; continue; } m++; } return count; } ~~~ ## 三、钱币找零 &emsp;&emsp;假设买一杯牛奶需要5元，顾客向你支付5 元、10 元或 20 元纸币，你需要判断是否能正确找零（开始时手头没有零钱）。例题：[860\. 柠檬水找零](https://leetcode-cn.com/problems/lemonade-change/)。 &emsp;&emsp;解题思路是先用面值最大的纸币来找零，不够的话再用更小一点的面值，直至完成找零或无法找零，[如下所示](https://codepen.io/strick/pen/dyGENvd) ~~~ function lemonadeChange(bills) { let five = 0, //5元纸币数量 ten = 0; //10元纸币数量 for (let bill of bills) { switch (bill) { case 5: five++; //增加5元纸币数量 break; case 10: if (five > 0) { //有5元才纸币能找零 five--; } else { return false; } ten++; break; case 20: if (five > 0 && ten > 0) { //用5元和10元两种纸币找零 five--; ten--; } else if (five >= 3) { //用3张5元纸币找零 five -= 3; } else { return false; } break; } } return true; } ~~~ ***** > 原文出处： [博客园-数据结构和算法躬行记](https://www.cnblogs.com/strick/category/1809992.html) 已建立一个微信前端交流群，如要进群，请先加微信号freedom20180706或扫描下面的二维码，请求中需注明“看云加群”，在通过请求后就会把你拉进来。还搜集整理了一套[面试资料](https://github.com/pwstrick/daily)，欢迎阅读。  推荐一款前端监控脚本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不仅能监控前端的错误、通信、打印等行为，还能计算各类性能参数，包括 FMP、LCP、FP 等。