&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 等。