简单题目

贪心算法总结就是一句话，局部最优推出整体最优
例如力扣上的这一道题：

LC455

  每个孩子有胃口g[i] ,饼干有尺寸s[i] ，求最多可以满足多少孩子的胃口？
  局部最优，就是满足一个孩子的胃口，用尽可能少的饼干满足胃口尽可能大的孩子，然后满足多个孩子，最终满足胃口数量达到最优

我们，可以首先将数组排序，然后，用大饼干开始满足大胃口，记录满足的个数，最终返回结果

class Solution {
   
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
   
        //局部最优推出全局最优解
        if(s.size()==0) return 0;
        int count =0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index=s.size()-1;
        for(int i=g.size()-1;i>=0;i--)
        {
   
            if(index>=0&&s[index]>=g[i])
            {
   
                index--;
                count++;
            }
        }
        return count;
    }
};

LC376

  永远记住，贪心的方法，局部最优推出整体最优，为了统计摆动序列的最大长度，所以，可以将一些破坏摆动性的数字删除，使其达到最大的摆动性，从实现上看，就是将连续下降和连续上升的坡上面只保留一个元素：

class Solution {
   
public:
    int wiggleMaxLength(vector<int>& nums) {
   
        //局部最优推出整体最优
        if(nums.size()<=1) return nums.size();
        int preDiff=0;
        int curDiff=0;
        int count=1;
        for(int i=0;i<nums.size()-1;++i)
        {
   
            curDiff=nums[i+1]-nums[i];
            if( (curDiff>0&&preDiff<=0)||(curDiff<0&&preDiff>=0) )
            {
   
                count++;
                preDiff=curDiff;
            }
        }
        return count;
    }
};

因为两个元素的时候，只能感受到一个峰，三个元素的时候，最多只能感受到两个峰，而题目需要统计的是序列的长度，因此，人为的初始化一个峰，让初始值=1，然后，遍历前后元素的相对大小，必须是差值交错出现的时候才满足题目条件；

股票问题

买卖股票的最佳时机II

  因为可以尽可能多的完成更多的交易，所以，一旦有利可图，就可卖出；翻译一下就是，统计相邻递增之差，累加起来，就是最终的最大利润；局部最优，有利就卖出，局部最优推出全局最优；

class Solution {
   
public:
    int maxProfit(vector<int>& prices) {
   
        int ans=0;
        for(int i=1;i<prices.size();++i)
        {
   
            if(prices[i]>prices[i-1])
            {
   
                ans+=prices[i]-prices[i-1];
            }
        }
        return ans;

    }
};

买卖股票的最佳时机含手续费

这题与上面一题的区别在于，需要手续费，因此不能频繁的买卖，所以，需要在最低点买入，最高点卖出；其实仍然可以采用上述的思想：局部最优，有利（当前价格>买入价格+手续费）就卖出，得到利润（当前价格-买入价格+手续费），如果明天还是有利，就把今天的手续费补回来；局部最优，整体上看，我们是在最低点买入，最高点卖出，只计算了一次手续费，从而全局最优；

class Solution {
   
public:
    int maxProfit(vector<int>& prices, int fee) {
   
        //如果没有手续费的限制，那就是统计相邻数字的正差之和；
        int minPrice=prices[0];
        int result=0;
        for(int i=1;i<prices.size();++i)
        {
   
            if(prices[i]<minPrice)  //更新最小价格
            {
   
                minPrice=prices[i];
            }
            else if(prices[i]<=minPrice+fee) //此时卖出亏本
            {
   
                continue;
            }
            else if(prices[i]>minPrice+fee) //更新利润，
            {
   
                result+=prices[i]-minPrice-fee; //把当前这一次卖出当做是最后一次
                minPrice=prices[i]-fee;//如果不是最后一次，那么下一次就将本次的手续费中和了，负负得正；
            }
        }
        return result;

    }
};

这里一步，当有利可图的时候，我们可以计算卖出得到的利润，当前记为今天，如果明天股票价格继续上涨，那么卖出仍然有利可图，明天计算利润的时候，result+=(prices[i]-fee) -minPrice-fee;就将今天减去的手续费补回来了，整体看，手续费就只计算了一次；也可以理解为，操作了无数次(股票价格需满足prices[i]>minPrice+fee，不然亏本)，只计算一次手续费

            else if(prices[i]>minPrice+fee) //更新利润，
            {
   
                result+=prices[i]-minPrice-fee; //把当前这一次卖出当做是最后一次
                minPrice=prices[i]-fee;//如果不是最后一次，那么下一次就将本次的手续费中和了，负负得正；
            }

两个维度制衡问题

分发糖果

class Solution {
   
public:
    int candy(vector<int>& ratings) {
   
        //两次比较
        vector<int> ans(ratings.size(),1);
        //首先比较左边，比左边大，拿更多的糖果
        for(int i=1;i<ratings.size();++i)
        {
   
            if(ratings[i]>ratings[i-1])
            {
   
                ans[i]=ans[i-1]+1;
            } 
        }
        //然后比较右边，比右边大，拿更多的糖果
        for(int i=ratings.size()-2;i>=0;--i)
        {
   
            if(ratings[i]>ratings[i+1])
            {
   
                ans[i]=max(ans[i],ans[i+1]+1);
            } 
        }
        return accumulate(ans.begin(),ans.end());
    }
};

406 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

思路：本题也是两个维度，一个是身高h,另一个是排在前面的人数k;思路是，先根据身高排序，然后根据k进行插入；插入的时候，如果是数组，定位插入位置时间复杂度O(1)，插入时间复杂度为O(n^2^)，而链表的话，定位插入位置时间复杂度O(n)，插入时间复杂度O(1);

class Solution {
   
private:
    static bool cmp(const vector<int> a,const vector<int> b)
    {
   
        if(a[0]==b[0])
            return a[1]<b[1]; //身高相同，就按照k来排列，k小的在前面
        return a[0]>b[0]; //按照身高来排列
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) 
    {
   
        //首先排序
        sort(people.begin(),people.end(),cmp);
        list<vector<int>> ans;
       for(int i=0;i<people.size();++i)
       {
   
           int position=people[i][1];
           auto it=ans.begin();
           while(position--)
            it++;
            ans.insert(it,people[i]);
       }
       return vector<vector<int>>(ans.begin(),ans.end());
    }
};