貪心算法：
貪心無套路撬统，局部最優(yōu)推全局最優(yōu)。
455.分發(fā)餅干
思路：
盡量大餅干給大需求
先排序敦迄，兩個數(shù)組都從小到大順序恋追。用num記錄多少個孩子吃到了餅干。如果沒有孩子或沒有餅干罚屋，直接返回苦囱。int i,j分別為兩個數(shù)組size-1。進(jìn)入循環(huán)脾猛，循環(huán)條件是還有孩子和餅干撕彤，如果孩子的需求小于等于餅干，則計數(shù)加一猛拴，孩子和餅干減一羹铅，否則孩子減一瞧柔。最后返回計數(shù)num。
看視頻后：
這里的局部最優(yōu)就是大餅干喂給胃口大的睦裳，充分利用餅干尺寸喂飽一個造锅，全局最優(yōu)就是喂飽盡可能多的小孩。
無論有沒有吃到廉邑，小孩子都會減一哥蔚。因此用小孩的數(shù)組下標(biāo)作為循環(huán)條件，用餅干和小孩的匹配做判斷條件蛛蒙。
for(int?i=g.size()-1;i>=0;i--)
????????{
????????????if(index>=0?&&?s[index]>=g[i])
????????????{
????????????????result++;
????????????????index--;
????????????}
????????}
也可以小餅干喂小胃口糙箍，則循環(huán)順序變化。
376. 擺動序列
思路：
建立數(shù)組minor, int i=1牵祟。在i<nums.size()的循環(huán)內(nèi)深夯，分成三種情況：如果相差大于0，則放入差值進(jìn)minor并進(jìn)行循環(huán)尋找下一個和i-1相差小于等于0的下標(biāo)诺苹；如果相差小于0則放進(jìn)minor并進(jìn)行循環(huán)找下一個和i-1相差大于等于0的下標(biāo)咕晋；其他情況（等于0）則i++。最后返回minor.size()+1;
看視頻后：
局部最優(yōu)：刪除單調(diào)坡度上的節(jié)點（不包括單調(diào)坡度兩端的節(jié)點）收奔，那么這個坡度就可以有兩個局部峰值掌呜。
整體最優(yōu)：整個序列有最多的局部峰值，從而達(dá)到最長擺動序列坪哄。
只需要統(tǒng)計數(shù)組的峰值數(shù)量就可以了,因此不需要建立數(shù)組质蕉。
在計算是否有峰值的時候，大家知道遍歷的下標(biāo) i 翩肌，計算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）模暗，如果prediff < 0 && curdiff > 0或者prediff > 0 && curdiff < 0此時就有波動就需要統(tǒng)計。
有三種情況：
情況一：上下坡中有平坡
情況二：數(shù)組首尾兩端
情況三：單調(diào)坡中有平坡
class?Solution?{
public:
????int?wiggleMaxLength(vector<int>&?nums)?{
????????if?(nums.size()?<=?1)?return?nums.size();
????????int?curDiff?=?0;?//?當(dāng)前一對差值
????????int?preDiff?=?0;?//?前一對差值
????????int?result?=?1;??//?記錄峰值個數(shù)念祭，序列默認(rèn)序列最右邊有一個峰值
????????for?(int?i?=?0;?i?<?nums.size()?-?1;?i++)?{
????????????curDiff?=?nums[i?+?1]?-?nums[i];
????????????//?出現(xiàn)峰值
????????????if?((preDiff?<=?0?&&?curDiff?>?0)?||?(preDiff?>=?0?&&?curDiff?<?0))?{
????????????????result++;
????????????????preDiff?=?curDiff;?//?注意這里兑宇，只在擺動變化的時候更新prediff
????????????}
????????}
????????return?result;
????}
};
53. 最大子序和
思路：
1. 兩個for循環(huán)進(jìn)行遍歷，但是超時了
看視頻后：
本題貪心貪在sum如果小于0則會使新的數(shù)減小棒卷，因此如果sum<0的時候就重新從0開始計數(shù)顾孽。用result每次比較記錄較大值祝钢。
int?maxSubArray(vector<int>&?nums)?{
????????int?result=INT_MIN;
????????int?count=0;
????????for(int?i=0;i<nums.size();i++){
????????????count+=nums[i];
????????????if(count>result)
????????????????result=count;
????????????if(count<=0)
????????????????count=0;
????????}
????????return?result;
????}
