一、贪心算法的主要特点

在刷题过程中，贪心算法的题目一般没有固定的套路，所以其最大的难点就是如何实现局部最优。

而实现局部最优的方法也因题而异，有时候就是常识性的推导。

我们唯一可以做的，就是

手动模拟一下，感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

贪心算法一般分为如下四步：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。

二、贪心算法的经典题目（简单难度）

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
455	分发饼干（简单难度）	一对一，将不同尺寸的饼干分给不同胃口的孩子，尽可能满足最多孩子的胃口	小尺寸饼干分给小胃口孩子	https://leetcode-cn.com/problems/combinations/
1005	K次取反后最大化的数组和（简单难度）	将数组中的数进行k次取相反数后数组和最大，可以对同一个数反复取相反数。	数组中的负数取反，负数的绝对值越大优先级越高；然后反复取同一个最小的非负数（实现上需要将数组按绝对值大小排序）	https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
860	柠檬水找零（简单难度）	付钱找零，判断是否可以全部正确找零	多种找零情况下优先找面额大的钞票	https://leetcode-cn.com/problems/lemonade-change/

1、455 分发饼干

该题目的目标是满足尽可能多的孩子的胃口，那么对于每个孩子就是尽可能用最小尺寸的饼干来其胃口，即尽可能做到大饼干喂给大胃口孩子，小饼干喂给小胃口孩子。

那么我们的代码肯定要先将孩子按照胃口大小从小到大排序，将饼干按尺寸大小从小到大排序，即：

sort(g.begin(),g.end());
sort(s.begin(),s.end());

接下来就是遍历每个孩子，看当前饼干尺寸是否满足其胃口，满足则更新当前孩子和饼干并计数，不满足则更新当前饼干，总的算法如下：

int findContentChildren(vector<int>& g, vector<int>& s) {
        if(s.size()==0){
            return 0;
        }
        //孩子们的胃口排序，用最小的饼干满足尽可能多的孩子
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int j = 0; // 当前饼干序号
        int count = 0;
        // 遍历每个孩子
        for(int i=0;i<g.size();){
            // 如果当前孩子胃口小于等于当前饼干尺寸
            if(g[i]<=s[j]){
                count++;//结果+1
                i++;//更新当前孩子
                //更新当前饼干
                j++;
                if(j>=s.size()){
                    break;
                }
            }
            // 如果当前孩子胃口大于当前饼干尺寸
            else{
                //更新当前饼干
                j++;
                if(j>=s.size()){
                    break;
                }
            }
        }
        return count;
    }

整理代码后，得：

int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = 0;
        for(int i = 0;i < s.size();++i){
            if(index < g.size() && g[index] <= s[i]){
                index++;
            }
        }
        return index;
    }

2、1005 K次取反后最大化的数组和

该题目是将数组中的数进行k次取相反数后数组和最大，可以对同一个数反复取相反数。

根据题意可知，使最后数组和最大的策略是：

1、首先将数组中的负数取反，负数的绝对值越大优先级越高；

2、如果此时数组中负数全取反后，k依旧不为0：

如果k是偶数，则不用管，对同一个数进行偶数次取反还是原数

如果k是奇数，则将此时数组中最小的数取反即可。

我们的策略有了，接下来就是实现，首先需要将数组按绝对值从大到小排列，这样就可以对负数进行取反；

然后判断k是奇数或者偶数即可：

static bool cmp(int a, int b) {
        return abs(a) > abs(b); //大于表示从大到小
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        // 将数组按照绝对值进行从小到大的排序
        sort(nums.begin(), nums.end(), cmp);
        // 遍历数组，将负数变为整数，同时K--
        for (int i = 0; i <nums.size(); i++) { 
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        // 如果此时k依旧为奇数，则将最小的非负数反复转换为其相反数即可
        if (k % 2 == 1) {
            nums[nums.size() - 1] *= -1; 
        }
        int result = 0;
        // 求最大数组和
        for (int a : nums) {
            result += a; 
        }
        return result;
    }

本题的难点可能就是如何将数组按照想要的按绝对值大小进行排序。

3、860 柠檬水找零

有如下三种情况：

情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

bool lemonadeChange(vector<int>& bills) {
        int five_count = 0;//5美元的数量
        int ten_count = 0;//10美元的数量
        // 遍历账单
        for(int bill:bills){
            // 如果当前顾客付了5美元
            if(bill==5){
                five_count++;
            }
            // 如果当前顾客付了10美元
            else if(bill==10){
                ten_count++;
                // 如果有1张以上的5元零钱
                if(five_count>0){
                    five_count--;
                }
                else{
                    return false;
                }
            }
            // 如果当前顾客付了20美元
            else if(bill==20){
                // 如果同时有5元和10元的零钱
                if(ten_count>0&&five_count>0){
                    ten_count--;
                    five_count--;
                }
                // 如果只有3张以上的5元零钱
                else if(five_count>=3){
                    five_count-=3;
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }