贪心专题二

5/29

T435 无重叠区间

1、这一题需要再次细致研究证明

2、和前面两题不同，它每次考虑的是当前较大的端点值，而非二维排序后的最值

3、两种解法，分别聚焦保留区间与舍弃区间：

代码一

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 按区间右端点从小到大排序，优先保留结束最早的区间。
        // 这样可以给后面的区间留下更多空间，是本题的贪心策略。
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        // keep 表示当前最多能保留下来的不重叠区间数量。
        int keep = 1;
        // lastEnd 表示上一个被保留区间的右端点。
        int lastEnd = intervals[0][1];

        for (int i = 1; i < intervals.size(); ++i) {
            // 当前区间的左端点 >= 上一个保留区间的右端点，说明不重叠。
            // 注意：[1,2] 和 [2,3] 只在一点接触，也算不重叠。
            if (intervals[i][0] >= lastEnd) {
                ++keep;
                lastEnd = intervals[i][1];
            }
        }

        // 总区间数 - 最多能保留的区间数 = 最少需要删除的区间数。
        return intervals.size() - keep;
    }
};

代码二

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 按左端点从小到大排序，方便从左到右判断相邻区间是否重叠。
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

        // remove 表示已经删掉的区间数量。
        int remove = 0;
        // lastEnd 表示当前保留下来的区间中，最后一个区间的右端点。
        int lastEnd = intervals[0][1];

        for (int i = 1; i < intervals.size(); ++i) {
            // 当前区间左端点 < lastEnd，说明和前面保留的区间发生重叠。
            if (intervals[i][0] < lastEnd) {
                // 两个区间重叠时，必须删掉一个。
                // 为了尽量不影响后面的区间，删掉右端点更大的那个。
                ++remove;
                lastEnd = min(lastEnd, intervals[i][1]);
            } else {
                // 不重叠时，当前区间可以保留，更新最后保留区间的右端点。
                lastEnd = intervals[i][1];
            }
        }

        return remove;
    }
};

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

1、这一题正好印证了上一题的结论：想不到思路的时候，先排序。本题的难度在于直觉性的排序会让人觉得有很多反例，犹豫是否是正确的。具体面试时可以先写，AC了再来思考正确性证明。

2、核心逻辑：按照右端点从小到达排序，每次先选最小的射箭，干掉一系列符合要求的左端点，遇到不符合时再更新右端点。注意：假设有这样一个排序后的 [1,6] [2,8] [7,12] [3,15] [10,16]

假如一开始射箭6，左端点7时射出第二支箭，12。但后面又出现【3，15】。这个3其实是符合6的，所以不需要12，但毕竟有个7需要12，我们现在只需要让【3，15】也能被12干掉。之前的要求是3<=6,现在是3<=12，放宽松了，故不必担心此等情况。

3、代码如下：

class Solution {
public:

    int findMinArrowShots(vector<vector<int>>& points) {

        if (points.empty())
            return 0;

        // 按右端点升序排序
        sort(
            points.begin(),
            points.end(),
            [](const vector<int>& a, const vector<int>& b)
            {
                return a[1] < b[1];
            }
        );

        int ans = 1;

        // 第一支箭射在第一个区间右端点
        long long pos = points[0][1];

        for (int i = 1; i < points.size(); i++)
        {
            // 当前气球无法被之前那支箭射爆
            if (points[i][0] > pos)
            {
                ans++;

                // 新箭射在当前区间右端点
                pos = points[i][1];
            }
        }

        return ans;
    }
};

4、非常关键的一种正确性证明法：证明这样做不会比最优解差

算法

按右端点从小到大排序。

每次选择当前还没被射爆的第一个气球 [l, r]， 把箭射在它的右端点 r。

然后所有满足 start <= r 的气球都会被这支箭射爆。 继续处理下一个没被射爆的气球。

证明：为什么这是最少支箭？ 设排序后，当前还没被射爆的第一个气球是：

[l, r]

因为它还没被射爆，所以我们无论如何都必须再射一支箭来射爆它。 也就是说：

最优解中也必须有一支箭落在 [l, r] 内

假设最优解中这支箭射在：

x

其中：

l <= x <= r

现在我们把这支箭从 x 移到 r。 要证明这样不会变差。

很简单：对于【l r】[]的区间，都射不到。对于【l [r】]的区间，r会比x射到更多可能的，也就是优于或至少一样，对于假定最优解X。对于【l [] r】或[【l ] r】这种右边界小于r的，chu 初看x会更优，实则由于r已经是所有右边界里的最小值，这两种情况根本不会出现。综上，按照算法每次循环选值，必然不会差于想要干掉当前气球（而这是必须做到的）假定最优解。证毕。

T406 根据身高重建队列

1、这一题非常巧妙，一开始我只想到两个特性： //对于y为同一值的人，按照身高顺序由小到大排列。也就是每一组y里，不管身高连不连续，在整个视角下都应该非递减 //对于同样的身高，y值越大的放在越右侧

2、然而，这不足以解题。学习题解后，这里面涉及一个非常有趣的证明：假如我们先按照身高大到小、k值小到大的顺序排序，再按照这个序列依次执行插入，则队列已有的所有元素一定大于等于每次新插入的元素，也就是新插入元素时只需插入到位置坐标为K的地方即可满足要求。每轮循环类推，最终解亦满足。

3、代码如下：

class Solution {
public:

    // 排序规则：
    // 1. 身高高的优先（降序）
    // 2. 身高相同时，k小的优先（升序）
    static bool cmp(vector<int>& a, 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>> ans;

        // 依次处理排序后的每个人
        for (auto& p : people)
        {
            // p[0] = 身高
            // p[1] = 前面需要有多少个身高 >= 自己的人

            // 由于已经按身高降序排列，
            // 当前队列中的所有人身高都 >= 当前人
            //
            // 因此直接插入到下标 p[1] 的位置即可：
            // 前面恰好有 p[1] 个人，
            // 且这些人一定满足身高 >= 当前人
            ans.insert(
                ans.begin() + p[1],
                p
            );
        }

        return ans;
    }
};

4、注意这里insert会挪动整个数组，因此题干给的总人数只有2000，配合高复杂度计算。

5、从这一题可以学到，当我们没有思路时，找一些特性排序可以提供灵感，先直觉再证明。

5/27

T860 柠檬水找零

1、这一题看起来很简单，思路如下： //从左到右遍历数组，维护三个数值：5 10 20当前已有钞票数 //对于每一个新顾客，更新这三个数值。特别的，如果是10，观察5的数值是否大于等于1，如果是20，观察10+5或5+5+5是否存在。更新三个数值

2、实际上，这是存在坑的，即需使用贪心逻辑的地方：在遇到20账单时必须优先找10+5，再寻找5+5+5，因为5的灵活性更大，能用次一点的满足就把更好的留到后面。

局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

3、最终代码如下：

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {

        // 当前拥有的 5、10、20 美元数量
        int five = 0;
        int ten = 0;
        int twenty = 0;

        // 按顾客顺序处理
        for (int bill : bills) {

            // 顾客给5元，不需要找零
            if (bill == 5) {
                five++;
            }

            // 顾客给10元，需要找5元
            else if (bill == 10) {

                // 没有5元无法找零
                if (five < 1)
                    return false;

                five--;
                ten++;
            }

            // 顾客给20元，需要找15元
            else {

                // 优先使用 10 + 5
                if (ten >= 1 && five >= 1) {
                    ten--;
                    five--;
                }

                // 否则使用 5 + 5 + 5
                else if (five >= 3) {
                    five -= 3;
                }

                // 都无法满足
                else {
                    return false;
                }

                twenty++;
            }
        }

        return true;
    }
};

5/26

T135 分发糖果

1、这一题虽为困难标签，但思路不难，我的初始思路可以AC： //统计连续上升/下降相邻峰的个数，若为连续的同方向的峰，每次糖果数都要在前一个基础上加一，直到方向改变或值相同，此时都赋值新糖果数为1 //注意，若从上升/连续改为下降峰，检测到下降峰结束后，将最小分数的孩子糖果数赋值为1，左侧同一个下降峰上的糖果数加上1和原先那个孩子糖果数的差值

2、本题代码如下：

class Solution {
public:
    int candy(vector<int>& ratings) {

        int n = ratings.size();

        // 每个孩子至少一个糖果
        vector<int> candy(n,1);

        int i=1;

        while(i<n){

            // 平坡
            if(ratings[i]==ratings[i-1]){

                candy[i]=1;

                i++;

                continue;
            }

            // 上升峰
            while(
                i<n &&
                ratings[i]>ratings[i-1]
            ){

                candy[i]=candy[i-1]+1;

                i++;
            }

            // 记录下降峰起点
            int peak=i-1;

            // 下降峰长度
            int down=0;

            while(
                i<n &&
                ratings[i]<ratings[i-1]
            ){

                down++;

                i++;
            }

            // 存在下降峰
            if(down>0){

                // 最低点赋值1
                candy[peak+down]=1;

                // 从右往左补
                for(
                    int j=peak+down-1;
                    j>=peak;
                    j--
                ){

                    candy[j]=max(
                        candy[j],
                        candy[j+1]+1
                    );
                }
            }
        }

        int sum=0;

        for(int x:candy)
            sum+=x;

        return sum;
    }
};

3、有两个重要的坑：一个是 candy[j]=max( candy[j], candy[j+1]+1 ); 这里要防止下降峰从有至左赋值时把上升峰的那一个也干掉了，得取最大值。例如： [1,3,4,5,2]

再就是对于下降峰，不能直接一个个减，有可能会减到负数，我的处理方式是最低点赋值糖果数1，往左侧++，最后再处理方才那个坑。

T134 加油站

1、这一题我一开始认为不必按照贪心做，因为核心是节省重复计算浪费的时间，直接用前缀和思想即可。

2、我的初始思路如下： //用gas减去cost对应的值，存储为新数组 //从第一个加油站开始，计算后续g-c的每一节点的累加和 //保持一个累加和最小值，若为负数，pass该加油点 //继续第二个加油站，把最小累加和减去1到2加油站之间的g-c差值，对比上一个循环最后累加和+ 1到2之间的g-c差值，取两者最小值更新为累加和最小值 //观察是否为负数，若是，pass，若不是，返回该编号 //直到遍历结束，若都无，返回-1

这个思路的错误点：移动起始位置后，原先的累加和最小值可能不存在了（正好是开头两个加油站时），此时我们并未记录第二小值，因此算法无法继续；若每次都重新计算累加和最小值，则和暴力解法无区别，会超时。

3、可以观察到，该问题和单调队列要解决的滑动窗口问题很像，尝试采用该方法优化时间复杂度，AC：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();

        vector<int> diff(2*n);

        // 环展开两倍
        for(int i=0;i<n;i++){

            diff[i]=gas[i]-cost[i];

            diff[i+n]=diff[i];
        }

        // 前缀和
        vector<long long> pre(2*n+1,0);

        for(int i=1;i<=2*n;i++)
            pre[i]=pre[i-1]+diff[i-1];

        deque<int> q;

        // 初始化第一个窗口
        for(int i=1;i<=n;i++){

            while(!q.empty() &&
                  pre[q.back()]>=pre[i])
                q.pop_back();

            q.push_back(i);
        }

        // 枚举起点
        for(int start=0;start<n;start++){

            long long base=pre[start];

            // 当前窗口最小值
            long long minsum=
                pre[q.front()]-base;

            if(minsum>=0)
                return start;

            // 删除过期
            while(!q.empty() &&
                  q.front()==start+1)
                q.pop_front();

            int nxt=start+n+1;

            if(nxt<=2*n){

                while(!q.empty() &&
                      pre[q.back()]>=pre[nxt])
                    q.pop_back();

                q.push_back(nxt);
            }
        }

        return -1;
    }
};

4、然而，这样做的缺点很明显：时间效率仍然很低，最优解依旧应当考虑贪心算法。贪心解法的核心和累加和很像，具体代码如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();

        int sum = 0;

        // 总累加和
        int minsum = INT_MAX;

        // 最小前缀和对应位置
        int minpos = -1;

        for(int i=0;i<n;i++){

            sum += gas[i]-cost[i];

            if(sum < minsum){

                minsum = sum;

                minpos = i;
            }
        }

        // 总油量不足
        if(sum < 0)
            return -1;

        // 最小前缀和后一个点
        return (minpos+1)%n;
    }
};

5、贪心算法核心是利用了一个定理：假设总g大于总c，无论如何分布，都一定存在可以跑完一圈的起点，且寻找该解的方式就是利用最小前缀和。该定理证明过程如下：

设： diff[i] = gas[i] - cost[i]

并设前缀和：

S[0] = 0 S[1] = diff[0] S[2] = diff[0] + diff[1] … S[n] = diff[0] + … + diff[n-1]

如果：

S[n] = sum(gas) - sum(cost) >= 0

说明总油量不亏。 现在找到前缀和最小的位置：

S[k] 是所有 S[0], S[1], …, S[n] 中的最小值

那么选择：

start = k

作为起点。 为什么可行？ 从 k 出发，到后面任意一个位置 j，车上的油量等于：

S[j] - S[k]

因为 S[k] 是最小前缀和，所以：

S[j] - S[k] >= 0

因此从 k 出发走到后面不会断油。

如果走到数组末尾后继续绕回前面，到某个位置 j < k，此时油量等于：

S[n] - S[k] + S[j]

由于：

S[n] >= 0

且：

S[j] >= S[k]

所以：

S[n] - S[k] + S[j] >= 0

因此绕回前面也不会断油。 所以只要：

sum(gas) >= sum(cost)

就一定存在一个可行起点。这个起点就是前缀和最低点的后一个位置。

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

1、本题没什么难度，直接逻辑分析可得排序+奇偶处理解法。

2、但是，有个坑容易掉入：若减去负数元素数量后k有剩余且为奇数，这时不能直接反转最小原始数组非负数，而是该同时考虑新数组由负数转为正数中的最小值，因为这个绝对值可能更小，且同为正数。以及，对于偶数组，由于最终结果为无影响，不必模拟流程，直接跳过处理即可。

3、代码如下：

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {

        // 从小到大排序
        sort(nums.begin(), nums.end());

        // 优先翻转负数
        for (int i = 0; i < nums.size() && k > 0; i++) {

            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
            else break; // 后面全非负，直接退出
        }

        // 重新排序，找最小值
        sort(nums.begin(), nums.end());

        // 若剩余次数为奇数
        // 只能再翻转一次最小值
        if (k % 2 == 1)
            nums[0] = -nums[0];

        // 求和
        int sum = 0;

        for (int x : nums)
            sum += x;

        return sum;
    }
};