先來看第一道：860. 檸檬水找零 - 力扣（LeetCode）

有如下三種情況：

• 情況一：賬單是5，直接收下。
• 情況二：賬單是10，消耗一個5，增加一個10
• 情況三：賬單是20，優先消耗一個10和一個5，如果不夠，再消耗三個5

此時大家就發現 情況一，情況二，都是固定策略，都不用我們來做分析了，而唯一不確定的其實在情況三。

而情況三邏輯也不復雜甚至感覺純模擬就可以了，其實情況三這里是有貪心的。

賬單是20的情況，為什么要優先消耗一個10和一個5呢？

因為美元10只能給賬單20找零，而美元5可以給賬單10和賬單20找零，美元5更萬能！

所以局部最優：遇到賬單20，優先消耗美元10，完成本次找零。全局最優：完成全部賬單的找零。

局部最優可以推出全局最優，并找不出反例，那么就試試貪心算法！

C++代碼如下：

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0, twenty = 0;for (int bill : bills) {// 情況一if (bill == 5) five++;// 情況二if (bill == 10) {if (five <= 0) return false;ten++;five--;}// 情況三if (bill == 20) {// 優先消耗10美元，因為5美元的找零用處更大，能多留著就多留著if (five > 0 && ten > 0) {five--;ten--;twenty++; // 其實這行代碼可以刪了，因為記錄20已經沒有意義了，不會用20來找零} else if (five >= 3) {five -= 3;twenty++; // 同理，這行代碼也可以刪了} else return false;}}return true;}
};

然后看第二道：406. 根據身高重建隊列 - 力扣（LeetCode）

按照身高排序之后，優先按身高高的people的k來插入，后序插入節點也不會影響前面已經插入的節點，最終按照k的規則完成了隊列。

所以在按照身高從大到小排序后：

局部最優：優先按身高高的people的k來插入。插入操作過后的people滿足隊列屬性

全局最優：最后都做完插入操作，整個隊列滿足題目隊列屬性

C++代碼如下：

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort (people.begin(), people.end(), cmp);vector<vector<int>> que;for (int i = 0; i < people.size(); i++) {int position = people[i][1];que.insert(que.begin() + position, people[i]);}return que;}
};

然后看最后一道：452. 用最少數量的箭引爆氣球 - 力扣（LeetCode）

這道題好像原來寫過。

部分最優：當氣球出現重疊，一起射，所用弓箭最少。全局最優：把所有氣球射爆所用弓箭最少。

算法確定下來了，那么如何模擬氣球射爆的過程呢？是在數組中移除元素還是做標記呢？

如果真實的模擬射氣球的過程，應該射一個，氣球數組就remove一個元素，這樣最直觀，畢竟氣球被射了。

但仔細思考一下就發現：如果把氣球排序之后，從前到后遍歷氣球，被射過的氣球僅僅跳過就行了，沒有必要讓氣球數組remove氣球，只要記錄一下箭的數量就可以了。

以上為思考過程，已經確定下來使用貪心了，那么開始解題。

為了讓氣球盡可能的重疊，需要對數組進行排序。

那么按照氣球起始位置排序，還是按照氣球終止位置排序呢？

其實都可以！只不過對應的遍歷順序不同，我就按照氣球的起始位置排序了。

既然按照起始位置排序，那么就從前向后遍歷氣球數組，靠左盡可能讓氣球重復。

從前向后遍歷遇到重疊的氣球了怎么辦？

如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭。

class Solution {
private:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp);int result = 1; // points 不為空至少需要一支箭for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) {  // 氣球i和氣球i-1不挨著，注意這里不是>=result++; // 需要一支箭}else {  // 氣球i和氣球i-1挨著points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重疊氣球最小右邊界}}return result;}
};