贪心算法是一种常见的算法思想，其特点就是通过每次都选择局部最优来达到实现全局最优的目的。

例如让你从一堆钞票中拿走10张，你为了达到拿到最大金额的目的，必定会每次都拿走最大面额的钞票，这就是贪心算法的思想。

一、贪心算法的序列题目（中等难度）

LeetCode题目	相关题目类型	题目思路	相关链接
53	最大子序和（简单难度）	当连续和为负数的时候就放弃，重新开始计数	https://leetcode-cn.com/problems/maximum-subarray/
376	摆动序列（中等难度）	摆动序列就是当前差值和上一个差值符号相反，但是注意开始序列可能为0	https://leetcode-cn.com/problems/wiggle-subsequence/
738	单调递增的数字（中等难度）	从右向左扫描数字，若发现当前数字比其左边一位（较高位）小，则把其左边一位数字减1，并将该位及其右边的所有位改成9	https://leetcode-cn.com/problems/monotone-increasing-digits/

53 最大子序和

贪心贪的是哪里呢？

如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

那有同学问了，区间终止位置不用调整么？如何才能得到最大“连续和”呢？

区间的终止位置，其实就是如果count取到最大值了，及时记录下来了。例如如下代码：

if (count > result) result = count;

这样相当于是用result记录最大子序和区间和（变相的算是调整了终止位置）。

	int maxSubArray(vector<int>& nums) {
        int maxSum = INT32_MIN;//要尽可能快的更新
        int curSum = 0;//当前子序和
        // 遍历数组
        for (int i = 0; i < nums.size(); i++) {
            curSum += nums[i];
            // 比较当前子序和和记录的最大子序和（相当于不断确定最大子序终止位置）
            if (curSum > maxSum) { 
                maxSum = curSum;
            }
            // 如果当前子序和小于等于零，立刻放弃该子序和，因为遇到负数一定是拉低总和
            if (curSum <= 0) {
                curSum = 0; // 相当于重置最大子序起始位置
            }
        }
        return maxSum;
    }

时间复杂度：O(n) 空间复杂度：O(1)

376 摆动序列

该题目的目标是从一个数组中找出满足摆动序列的最长子数组的长度，那么首先要解决的就是如何判断一个数组是否是摆动序列？

只要该数组里面的值符合以下特点就是一个摆动序列：

那么我们只要遍历数组，判断连续两个差值是否异号可初步判断是否是摆动序列。

但是在本题中我们是从数组中按照原始顺序找出一个最长摆动序列，我们的算法思路是：

首先定义一个结果数组作为最长序列，将数组的第一个元素加进去（确保数组元素大于1），然后判断加入第2个元素时结果数组是否还是摆动序列，是则加入不是则不加入跳过去，如下图：

则我们的算法代码如下：

int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()==1){
            return 1;
        }
        // 结果序列
        int curCha = 0;//当前差值
        int lastCha = 0;//前一个差值  
        vector<int> result;
        result.push_back(nums[0]);//默认第一个数在结果序列中
        // 遍历整个序列
        for(int i=1;i<nums.size();i++){
            curCha = nums[i]-nums[i-1];//计算当前序列
            // 如果上一个差值小于等于0并且当前差值大于0
            if(curCha>0&&lastCha<=0){
                result.push_back(nums[i]);
                lastCha = curCha;
            }
            // 上一个差值大于等于0并且如果当前差值小于0
            if(curCha<0&&lastCha>=0){
                result.push_back(nums[i]);
                lastCha = curCha;
            }
        }
        return result.size();
    }

738 单调递增的数字

整数转换为字符串：to_string(n)

字符串转换为整数：stoi(strNum)

数字字符可以直接进行比较：’8’<’9’

答案如下：

int monotoneIncreasingDigits(int n) {
        /**
        * 思路：
        *  从右向左扫描数字，若发现当前数字比其左边一位（较高位）小，
        *  则把其左边一位数字减1，并将该位及其右边的所有位改成9
        */
        string strNum = to_string(n);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();

        // 从右向左扫描数字，减小的第一个数设置为flag
        for (int i = strNum.size() - 1; i > 0; i--) {
            // 如果左边的数大于右边的数，说明此时没有单调递增
            if (strNum[i - 1] > strNum[i] ) {
                flag = i;//左边数
                strNum[i - 1]--;
            }
        }
        // 从左向右扫描数字，flag及其之后的数字都改为9
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        // 字符串数字转换为整数
        return stoi(strNum);
    }

二、贪心算法的股票题目（中等难度）

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
122	买卖股票的最佳时机II（中等难度）	一个股票在多天的价格走势数组，可以多次买入卖出，求获得的最大利润	价格数组中的相邻元素的差值，将差值为正的数都加起来	https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
714	买卖股票的最佳时机含手续费（中等难度）		最低值买，最高值（如果算上手续费还盈利）就卖	https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

122 买卖股票的最佳时机II

答案如下：

int maxProfit(vector<int>& prices) {
     /**
        * 思路：
        *  从左向右扫描数组，只要相邻数组是在增加的，则累计到利润中
        */
    int max_profit=0;
    // 遍历价格数组，找到相邻差值为正数，加到利润里
    for(int i=1;i<prices.size();i++){
        int cur=prices[i]-prices[i-1];
        if(cur>0){
            max_profit+=cur;
        }
    }
    return max_profit;
}

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

本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。

如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。

此时无非就是要找到两个点，买入日期，和卖出日期。

买入日期：其实很好想，遇到更低点就记录一下。
卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。

所以我们在做收获利润操作的时候其实有三种情况：

情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
情况三：不作操作，保持原有状态（买入，卖出，不买不卖）

贪心算法C++代码如下：

答案如下：

int maxProfit(vector<int>& prices, int fee) {
        int max_profit=0;
        int min_price=prices[0];
        // 遍历价格数组，找到相邻差值为正数，加到利润里
        for(int i=1;i<prices.size();i++){
            //  情况二：如果当天价格比之前的最低价格低，则记录买入价格
            if(min_price>prices[i]){
                min_price=prices[i];
            }
            // 情况三：如果当天价格比之前的最低价格高，但是利润小于手续费
            else if(min_price<=prices[i]&& prices[i] <= min_price + fee){
                continue;
            }
            // 如果当天价格比之前的最低价格高，而且利润大于手续费
            else if(prices[i] > min_price + fee){
                max_profit+=prices[i]-min_price-fee;//假设今天卖出，则利润等于当前价格-买入价格-手续费
                min_price = prices[i]-fee;// 情况一，这一步很关键假设明天还在涨，则明天求利润需要-今天收入（当前价格）+手续费
            }
        }
        return max_profit;
    }

时间复杂度：O(n)
空间复杂度：O(1)

从代码中可以看出对情况一的操作，因为如果还在收获利润的区间里，表示并不是真正的卖出，而计算利润每次都要减去手续费，所以要让minPrice = prices[i] - fee;，这样在明天收获利润的时候，才不会多减一次手续费！

大家也可以发现，情况三，那块代码是可以删掉的，我是为了让代码表达清晰，所以没有精简。

三、贪心算法的区间题目（中等难度）

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
55	跳跃游戏（中等难度）	跳跃覆盖范围可以不可以覆盖到终点的问题	每次移动取最大跳跃步数来得到最大的覆盖范围，每移动一个单位，就更新最大覆盖范围，一旦超过终点即可返回true。	https://leetcode-cn.com/problems/jump-game/
45	跳跃游戏II（中等难度）	当前覆盖范围和下一虚拟步的覆盖范围	在当前步覆盖范围不断前进，不断更新当前虚拟步的最大距离，当前覆盖范围走完且不是终点后，最小步数+1，更新当前步数的范围，如果此时当前步范围覆盖了数组终点则直接返回结果	https://leetcode-cn.com/problems/jump-game-ii/
134	加油站（中等难度）	起始站点存在则一定只有一个	如果curSum<0则[0,j]之间一定没有起始站点，排除思想	https://leetcode-cn.com/problems/gas-station/
452	用最少数量的箭引爆气球（中等难度）	二维数组排序，判断其中的区间边界是否重叠	先将气球按照起始位置或者终止排序；然后比较当前气球和前一个气球是否重合，不重合增加一只箭，重合则更新当前气球的右边界（取当前气球右边界和前一个气球右边界的最小值）	https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
435	无重叠区间（中等难度）	二维数组排序，判断其中的区间边界是否重叠	先将二维数组按照第二维数组的起点从小到大排序，然后比较当前区间的左边界和前一个区间的右边界来判断是否重叠，没有重叠跳过去，重叠了则结果+1，并且将当前区间的右边界取最小值（相当于默认删除右边界区间较大的那个重叠区间）	https://leetcode-cn.com/problems/non-overlapping-intervals/
763	划分字母区间（中等难度）	分割字符串，将同一个字母都圈在一个区间里	其等价于找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。所以我们可以遍历两次字符串，第1次遍历统计每个字符出现的最后位置；第2次遍历寻找分割点（字符最远下标与当前下标相等）.	https://leetcode-cn.com/problems/partition-labels/
56	合并区间（中等难度）	合并区间，可能连续n个区间可以合并在一起	需要一个二重循环，外层负责遍历两个相邻区间，内层负责判断是否是否重叠，重叠了则合并边界将其加入结果	https://leetcode-cn.com/problems/merge-intervals/

55 跳跃游戏

利用能量格子思路的答案如下：

bool canJump(vector<int>& nums) {
        /* 思路：想象你是那个在格子上行走的小人，格子里面的数字代表“能量”，你每走一个格子需要消耗一个“能量”。

        每次走到一个格子的时候，你检查现在格子里面的“能量”和你自己拥有的“能量”哪个更大，取更大的“能量”！ 如果你有更多的能量，你就可以走的更远啦！
        */
        // 只有一个元素，默认能达到
        if(nums.size()==1){
            return true;
        }
        int cur = nums[0];//获得的初始能量
        int i=0;//起步位置
        // 如果当前能量不为空则可以前进
        while(cur!=0){
            cur--;//能量-1
            cur = max(cur,nums[i]);// 如果当前能量比当前位置的能量小则
            i++;//位置+1
            if(i>=nums.size()){
                return true;
            }
        }
        return false;
    }

这个问题可以转换为跳跃覆盖范围可以不可以覆盖到终点的问题，即：

每次移动取最大跳跃步数来得到最大的覆盖范围，每移动一个单位，就更新最大覆盖范围，一旦超过终点即可返回true。

i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。

而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。

如果cover大于等于了终点下标，直接return true就可以了。

bool canJump(vector<int>& nums) {
        // 只有一个元素，默认能达到
        if(nums.size()==1){
            return true;
        }
        // i 每次只能在cover的范围内移动
        int cover=0;
        for(int i=0;i<=cover;i++){
            cover = max(i+nums[i],cover);//更新最大覆盖范围
            //检查覆盖范围是否超过终点
            if(cover>=nums.size()-1){
                return true;
            }
        }
        return false;
    }

45 跳跃游戏II

本题最后要计算最小步数，那么就要想清楚什么时候步数+1？

该代码需要统计两个覆盖范围：当前这一步的最大覆盖（确实采取了）curCover和下一虚拟步的最大覆盖（假设采取）nextCover。

具体代码如下：

int jump(vector<int>& nums) {
        // 只有一个元素，默认能达到
        if(nums.size()==1){
            return 0;
        }
        // i 每次只能在cover的范围内移动
        int result = 0;
        int curCover=0; // 当前这一步的覆盖范围的最远下标
        int nextCover=0;// 下一步的覆盖范围的最远下标
        //循环移动
        for(int i=0;i<nums.size();i++){
            nextCover = max(i+nums[i],nextCover);//更新最大覆盖范围
            //如果走到当前这一步的覆盖范围的终点
            if(i==curCover){
                // 如果不是数组终点
                if(i!=nums.size()-1){
                    result++;//步数+1
                    curCover=nextCover;//更新当前步数的范围
                    // 如果下一步范围覆盖了终点则直接返回
                    if(curCover>=nums.size()-1){
                        break;
                    }
                }else{
                    break;
                }
            }
        }
        return result;
    }

134 加油站

从本题的题目中首先要读懂两个设定：

如果可以跑完全程，这个起始站点是唯一的，不可能存在从多个起始站点出发都可以跑完全程的情况（题目说明中存在“如果题目有解，该答案即为唯一答案”）；
如果不可以跑完全程，说明其耗油总量（cost数组元素之和）一定大于加油总量（gas数组元素之和）。

然后我们可以知道：

从第i个站点出发跑到下一站点加油前，其加油gas[i],耗油cost[i]，相当于第i个站点给车贡献了res[i]=gas[i]-cost[i]的油量。

那么我们可以假设车子从第i=0个站点出发，然后到达第i+1个站点加油前的油量为curSum=res[0]+…+res[i];

如果此时curSum<0，说明车子无法达到第i+1个站点，

同时细想下我们也发现[0,j]中任何一个站点出发都不会走完全程了，因为从第0个站点走到第j+1都不够，那车子从第1个站点走到第j+1更不可能了，因为加油的站点更少了，所以出发站点只能在第j+1之后了。

我们给出代码：

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start=0; // 起始站点
        int curSum = 0; // 当前车子中的油量
        int totalSum = 0; // 全程一圈的总油量
        for(int i=0;i<gas.size();i++){
            // 从i站点出发获得的油量
            curSum+=gas[i]-cost[i];
            if(curSum <0)//车子没油了,说明[0,i]都不可以作为起始站点
            {
                start=i+1;//更换起始站点
                curSum = 0;
            }
            
            totalSum+=gas[i]-cost[i];//记录当前站点可以获得的油量
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }

在上述代码中，数组中的第i个站点如果是起始站点，则从第i个走到数组结束的第gas.size()-1个站点的过程中curSum和totalSum不能小于0。

totalSum>=0保证了一定存在一个起始站点，curSum<0则排除[0,i]之间的所有站点，第i+1走到数组重点没有出现curSum<0则必定是起始站点。

452 用最少数量的箭引爆气球

当气球出现重叠，一起射，所用弓箭最少；那么，把所有气球射爆的所用弓箭一定最少。

解答本题需要一些编程技巧，首先将气球排序，可以不删除气球数组通过遍历就能计算所用弓箭。

可以按照气球的起始位置排序，也可以按照气球的终止位置排序；

然后比较当前气球和前一个气球是否重合，不重合增加一只箭，重合则更新当前气球的右边界（取当前气球右边界和前一个气球右边界的最小值）；

当前思路示意图如下：

按照气球的起始位置排序的代码如下：

// 按照起始位置从小到大排列
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        /*输入一个二维数组（气球直径），返回一个整数（最小弓箭数）*/
        if(points.size()==1){
            return 1;
        }
        // 局部最优：当气球出现重叠，一起射，所用弓箭最少；
        // 全局最优：把所有气球射爆所用弓箭最少
        // 首先按照气球的起始位置排序
        sort(points.begin(),points.end(),cmp);
        
        int result=1;//至少有一个气球，所以至少需要一支箭
        for(int i=1;i<points.size();i++){
            // 如果前一个气球的右边界>当前气球的左边界,说明两个气球不重合
            if(points[i-1][1]<points[i][0]){
                result++;
            }
            // 当两个气球重合时,重新定义当前气球的右边界
            else{
                points[i][1]=min(points[i-1][1],points[i][1]);
            }
        }
        return result;
    }

注意：

cmp的参数传入最好设置为引用，因为不使用引用的话，排序过程中每次通过直接赋值到形参会造成大量的时间浪费

435 无重叠区间

这道题目和（452 用最少数量的箭引爆气球）非常像，同样先将二维数组按照第二维数组的起点从小到大排序

然后比较当前区间的左边界和前一个区间的右边界来判断是否重叠，没有重叠跳过去，重叠了则结果+1，并且将当前区间的右边界取最小值（相当于默认删除右边界区间较大的那个重叠区间）

代码如下：

static bool cmp(vector<int>& a,vector<int>& b){
        return a[0]<b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        /*输入一个二维数组，返回一个整数*/
        if(intervals.size()<=1){
            return 0;
        }
        int result=0;
        // 将二维数组按照第二维数组的起点从小到大排序
        sort(intervals.begin(),intervals.end(),cmp);
        for(int i=1;i<intervals.size();i++){
            // 如果相邻区间没有重叠
            if(intervals[i-1][1]<=intervals[i][0]){
                continue;
            }
            // 如果相邻区间重叠,则重新定义当前区间的右边界，取最小值，（相当于默认删除右边界区间较大的那个区间），
            else {
                result++;
                intervals[i][1] = min(intervals[i-1][1],intervals[i][1]);
            }
        }
        return result;
    }

763 划分字母区间

该题目就是分割字符串，将同一个字母都圈在一个区间里。

其等价于找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。

所以我们可以遍历两次字符串，

第1次遍历统计每个字符出现的最后位置；
第2次遍历寻找分割点（字符最远下标与当前下标相等）.

其整体思路如下:

接下来就是代码：

vector<int> partitionLabels(string s) {
        /*输入一个字符串，输出一个整数数组*/
        // 统计每个字符出现的最后位置
        int feq[27]={0};//字母频率数组
        for(int i=0;i<s.size();i++){
            feq[s[i]-'a']=i;
        }
        // 遍历字符串寻找分割点
        vector<int> result;
        int left = 0;
        int right = 0;
        for(int i=0;i<s.size();i++){
            right = max(right, feq[s[i] - 'a']); // 当前字符最远边界和之前字符的最远边界的最大值
            //如果当前位置是最远距离则是分割点
            if(i==right){
                result.push_back(right-left+1);//计算该长度
                left=i+1;//更新左边界
            }
        }
        return result;
    }

56 合并区间

该题目就是合并区间，需要注意一点的是两个相邻区间合并后的新区间可能还和之后的区间需要合并，所以说明了可能连续n个区间可以合并在一起。

这个n是不确定的，所以我们需要一个二重循环，外层负责遍历两个相邻区间，内层负责判断是否是否重叠，重叠了则合并边界将其加入结果。

合并只需要排序，确保遍历时每个不重叠的区间的左边界始终是最小的，不断更新右边界即可。

	// 按照区间左边界从小到大排序
    static bool cmp(const vector<int>& a,const vector<int>& b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        /*输入一个二维数组，输出一个二维数组*/
        if(intervals.size()==1){
            return intervals;
        }
        // 将数组排序
        sort(intervals.begin(),intervals.end(),cmp);
        vector<vector<int>> result;
        int start=0;
        int end=0;
        bool flag = false; // 标记最后一个区间有没有合并
        // 遍历每个区间
        for(int i=1;i<intervals.size();i++){
            start = intervals[i-1][0];    // 初始为i-1区间的左边界，一定是最小的，因为排序了
            end = intervals[i-1][1];      // 初始i-1区间的右边界，不一定是最大的，重叠时需要更新
            // 如果i区间和i-1区间重叠（需要保证i没有出界）
            while (i<intervals.size()  &&end>=intervals[i][0]) { // 合并区间
                end=max(end,intervals[i][1]);    // 更新右区间
                if (i == intervals.size() - 1) flag = true;   // 如果最后一个区间也发生重叠则标记下
                i++;                                // 继续合并下一个区间
            }
            result.push_back({start,end});
        }
        // 如果最后一个区间没有和前一个区间重叠，将需单独加入result
        if (flag == false) {
            result.push_back({intervals[intervals.size() - 1][0], intervals[intervals.size() - 1][1]});
        }
        return result;
    }