本文为学习代码随想录时所做的笔记，仅供学习参考，不做任何商业用途，若有侵权，请联系删除。

贪心算法（一）

什么是贪心

贪心的本质是选择每一阶段的局部最优解，从而达到全局最优。

贪心的套路（什么时候用贪心）

贪心算法并没有固定的套路

贪心的一般解题步骤

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

局部最优是什么，推导出全局最优

分发饼干

455. 分发饼干 - 力扣（LeetCode）

思路

这里的局部最优解就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

// 版本一 
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1; // 饼干数组的下标
        int result = 0;
        for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口 
            if (index >= 0 && s[index] >= g[i]) { // 遍历饼干 
                result++;
                index--;
            }
        }
        return result;
    }
};

摆动序列

376. 摆动序列 - 力扣（Leetcode）

思路1（贪心解法）

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

情况一：上下坡中有平坡

如图，可以统一规则，删除左边的三个2：

情况二：数组首尾两端

可以假设，数组最前面还有一个数字，那这个数字应该是什么呢？

之前我们在 讨论 情况一：相同数字连续 的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。

那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即preDiff = 0，如图：

// 版本一
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.size() - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            // 出现峰值
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
            }
            preDiff = curDiff;
        }
        return result;
    }
};

情况三：单调坡度有平坡

// 版本二 
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.size() - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            // 出现峰值
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
                preDiff = curDiff; // 注意这里，只在摆动变化的时候更新prediff 
            }
        }
        return result;
    }
};

最大子序列

53. 最大子数组和 - 力扣（Leetcode）

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

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

class Solution {
    public:
    	int maxSubArray(vector<int>& nums) {
            int result = INT32_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;
        }
};

买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣（Leetcode）

如果想到其实最终利润是可以分解的，那么本题就很容易了！

假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从第0天到第3天整体去考虑！

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

跳跃游戏

55. 跳跃游戏 - 力扣（Leetcode）

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

class Solution {
public:
	bool canJump(vector<int>& nums) {
		int cover = 0;
        if (nums.size() == 1)
            return true;  // 只有一个元素
        for (int i = 0; i <= cover; i ++) {
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1)
                return true;
        }
        
        return false;
	}
};

跳跃游戏II

45. 跳跃游戏 II - 力扣（Leetcode）

要从覆盖范围出发，不管怎么跳，覆盖范围一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数。

需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

// Version-1.0
class Solution {
    public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1)
            return 0;
        int curDistance = 0;  // 当前覆盖最远距离下标
        int ans = 0;  //记录走的最大步数
        int nextDistance = 0;  // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i ++) {
            nextDistance = max(nums[i] + i, nextDistance);
            if (i == curDistance) {  // 遇到所能覆盖的最远下标
                if (curDistance < nums.size() - 1) {  // 还没有到达终点，更新覆盖距离
                    ans ++;
                    curDistance = nextDistance;
                    if (curDistance >= nums.size() - 1)
                        break;  // 下一步的覆盖范围已经可以到达终点
                } else
                    break;
            }
        }
        return ans;
    }
};

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

1005. K 次取反后最大化的数组和 - 力扣（Leetcode）

• 将数组按照绝对值大小从大到小排序
• 从前向后遍历，遇到负数将其变为正数，同时K--
• 如果K还大于0，那么反复转变数值最小的元素，将K用完
• 求和

class Solution {
	static bool cmp(int a, int b) {
        return abs(a) > abs(b);
    }
    public:
    	int largestSumAfterKNegations(vector<int>& A, int K) {
            sort(A.begin(), A.end(), cmp);
            for (int i = 0; i < A.size(); i ++) {
                if (A[i] < 0 && K > 0) {
                    A[i] *= -1;
                    K --;
                }
            }
            if (K % 2 == 1)
                A[A.size() - 1] *= -1;
            int result = 0;
            for (int a : A)
                result += a;
            
            return result;
        }
};

加油站

134. 加油站 - 力扣（Leetcode）

暴力方法

class Solution {
    public:
    	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            for (int i = 0; i < cost.size(); i ++) {
                int rest = gas[i] - cost[i];
                int index = (i + 1) % cost.size();
                while (rest > 0 && index != i) {  // 模拟以i为起点行驶一圈 
                    rest += gas[index] - cost[index];
                    index = (index + 1) % cost.size();
                }
                // 如果以i为起点跑一圈，剩余流量>=0，返回该起始位置
                if (rest >= 0 && index == i)
                    return i;
            }
            return -1;
        }
};

贪心算法（方法一）

• 情况一：如果gas的综合小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
• 情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点
• 情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能将这个负数填平，能把这个负数填平的节点就是出发节点

class Solution {
    public:
    	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int curSum = 0;
            int min = INT_MAX;  // 从起点出发，油箱里的油量最小值
            for (int i = 0; i < gas.size(); i ++) {
                int rest = gas[i] - cost[i];
                curSum += rest;
                if (curSum < min) {
                    min = curSum;
                }
            }
            if (curSum < 0)  // 情况1
                return -1;
            if (min >= 0)  // 情况2
                return 0;
            for (int i = gas.size() - 1; i >= 0; i --) {  // 情况3
                	int rest = gas[i] - cost[i];
                	min += rest;
                	if (min >= 0) {
                    	return i;
                	}
            }
            return -1;
            
        }
}

贪心算法（方法二）

局部最优：当前累加rest[j]和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

分发糖果

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

这道题目一定是要确实一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。

先确定右边评分大于左边的情况（从前向后遍历）

局部最优：只要右边评分比左边大，右边的孩子就多一个糖果

全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。

for (int i = 1; i < ratings.size(); i ++) {
    if (ratings[i] > ratings[i - 1])
        candyVec[i] = candyVec[i - 1] + 1;
}

再确定左孩子大于右孩子的情况（从后向前遍历）

所以确定左孩子大于右孩子的情况一定要从后向前遍历！

class Solution {
    public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i ++) {
            if (ratings[i] > ratings[i - 1])
                candyVec[i] = candyVec[i - 1] + 1;
        }
        
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i --) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        //统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i ++)
            result += candyVec[i];
        
        return result;
    }
};

柠檬水找零

860. 柠檬水找零 - 力扣（Leetcode）

美元10只能给账单找零，而美元5可以给账单10和账单20找零，美元5是万能的

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

根据身高重建队列

406. 根据身高重建队列 - 力扣（Leetcode）

遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度，如果两个维度一起考虑一定会顾此失彼

按照身高来排序，身高一定是从大到小排。

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性，

全局最优：最后都做完插入操作，整个队列满足题目队列属性。

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

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);
        list<vector<int>> que;  // list底层是链表实现，插入效率比vector高
        for (int i = 0; i < people.size(); i ++) {
            int position = people[i][1];
            std::list<vector<int>>::iterator it = que.begin();
            while (position --) {  // 寻找再插入位置
                it ++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};

用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

局部最优：当气球出现重叠，一起射，所用弓箭最少；

全局最优：把所有气球射爆用的弓箭最少。

为了让气球尽可能的重叠，需要对数组进行排序，如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

class Solution{
private:
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0)
            return 0;
        sort(points.begin(), points.end(), cmp);
        
        int result = 1;  // need 1 arrow at least when ponints is empty
        for (int i = 1; i < points.size();  i ++) {
            if (points[i][0] > points[i-1][1]) {
                result ++;
            } else { // The two balloons are not close to each other
                points[i][1] = min(points[i-1][1], points[i][1]);
            }
        }
        return result;
    }
};