134. 加油站 - 力扣（LeetCode）

思路：算出當前的消耗的油量總數，如果花費大于油量表示無法到達。統計總花費最大的油耗總數，如果油耗總數大于或者等于0，表示全程沒有負花銷，直接從0起步。小于零就從后向前遍歷，當總最大油耗抹平就返回當時的下標

重點：使用min記錄從0開始的最大總油耗

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n=gas.size();int cur=0;int min=INT_MAX;for(int i=0;i<n;i++){int t=gas[i]-cost[i];cur+=t;if(cur<min){min=cur;}}if(cur<0){return -1;}if(min>=0){return 0;}for(int i=n-1;i>=0;i--){int t=gas[i]-cost[i];min+=t;if(min>=0){return i;}}return -1;}
};

135. 分發糖果 - 力扣（LeetCode）

思路：從前向后遍歷給右邊評分比左邊評分大的孩子分發一個糖果，從后向前遍歷給左邊比右邊大孩子分發糖果，同時比較左邊評分比右邊評分高的孩子的糖果數和右邊評分最高的糖果數，選最大值作為結果。

重點：左右兩個方向分開考慮，先左再右

class Solution {
public:int candy(vector<int>& ratings) {int n=ratings.size();vector<int>ans(n,1);for(int i=1;i<n;i++){if(ratings[i]>ratings[i-1]){ans[i]=ans[i-1]+1;}}for(int i=n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){ans[i]=max(ans[i+1]+1,ans[i]);}}int res=0;for(int x:ans){res+=x;}return res;}
};

860. 檸檬水找零 - 力扣（LeetCode）

思路：記錄5元錢的數量，當付的是10元時消耗1張5元。當付的是20元時如果有10元零錢，優先消耗一張10元和一張5元。沒有就消耗三張5元。然后判斷5元數量是否小于零，小于零表示無法完成找零

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five=0,ten=0;for(int a:bills){if(a==5){five++;}else if(a==10){five--;ten++;}else if(ten){ten--;five--;}else{five-=3;}if(five<0){return false;}}return true;}
};

406. 根據身高重建隊列 - 力扣（LeetCode）

思路：先按照身高從到小排序，再按照前k個人從小到大排序。然后新建一個隊列，從左到右按照前k個人插入到下標為k的地方

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++){que.insert(que.begin()+people[i][1],people[i]);}return que;}
};

總結

貪心就是以局部推全局并且沒有反例的情況，當遇到不同維度的貪心時，需要分開討論