【代码随想录】贪心算法

贪心算法基础

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

说实话贪心算法并没有固定的套路。

如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

一般数学证明有如下两种方法：

• 数学归纳法
• 反证法

看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。

面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。

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

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

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

分发饼干

题目：455

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

思路：对于孩子i，从饼干中找到一个刚刚满足的他的饼干大小。

将二者都排序，然后遍历饼干，小饼干先满足小胃口的。

局部最优：大饼干喂给胃口大的，小饼干喂给胃口小的

全局最优：喂饱尽可能多的小孩

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 对饼干和胃口都进行升序排列
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        // 遍历孩子和饼干
        // 挑选最小能够满足胃口的
        int result = 0;
        int child_index = 0;
        int cookie_index = 0;

        while (child_index < g.size() && cookie_index < s.size()) {
            if (s[cookie_index] < g[child_index]) {
                // 如果饼干不能满足胃口
                cookie_index++;
            } else {
                // 如果饼干能够满足胃口
                result++;
                child_index++;
                cookie_index++;
            }
        }

        return result;
    }
};

时间复杂度O(nlogn)；空间复杂度O(1)

摆动序列

题目：376

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

解法1：贪心算法：局部最优：删除单调递增的元素，尽量使得出现波峰和波谷

整体最优：波峰和波谷最多

这样最基本的计算增加子序列长度的条件就是：当前一个差值和后一个差值符号相反时就可以增加

另外需要考虑的是：当出现相等的情况时，即

情况一：上下坡中有平坡

例如 [1,2,2,2,1]这样的数组，如图：

它的摇摆序列长度是多少呢？ 其实是长度是 3，也就是我们在删除的时候 要不删除左面的三个 2，要不就删除右边的三个 2。

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

在图中，当 i 指向第一个 2 的时候，prediff > 0 && curdiff = 0 ，当 i 指向最后一个 2 的时候 prediff = 0 && curdiff < 0。

如果我们采用，删左面三个 2 的规则，那么 当 prediff = 0 && curdiff < 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。

所以我们记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)，为什么这里允许 prediff == 0 ，就是为了 上面我说的这种情况。

另外需要考虑的是计算两个差值需要至少三个数，当数组只有两个数时应该如何处理：
情况二：单独处理两个元素

可以直接将两个元素的数组列出来，也可以加入到上面的情况中。

例如序列[2,5]，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。

因为我们在计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。

这里我们可以写死，就是 如果只有两个元素，且元素不同，那么结果为 2。

不写死的话，如何和我们的判断规则结合在一起呢？

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

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

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

针对以上情形，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）

情况三：单调坡度有平坡

在版本一中，我们忽略了一种情况，即 如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]，如图：

图中，我们可以看出，版本一的代码在三个地方记录峰值，但其实结果因为是 2，因为 单调中的平坡 不能算峰值（即摆动）。

之所以版本一会出问题，是因为我们实时更新了 prediff。

那么我们应该什么时候更新 prediff 呢？

我们只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。

思路2：贪心：这里的贪心是计算出所有差值，要求差值必须是一个大于0，下一个小于0.同样是能够使得波峰和波谷最多。

分别计算以正数和负数差值开始的序列，取最长的最为答案。

另外需要注意，如果找不到正数和负数差，说明全都是相等元素。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        // 边界检查
        int len = nums.size();
        if (len == 0) return 0;
        else if (len == 1) return 1;

        vector<int> diff;
        // 计算差值
        for (int i = 1; i < len; i++)
            diff.push_back(nums[i] - nums[i - 1]);

        // 第一个差值为正的最长序列
        int pre = -1;
        bool pos_flag = true; // 表示是否有正数的差
        // 找到第一个正值
        int i = 0;
        for (; i < diff.size(); i++) {
            if (diff[i] > 0) {
                pre = diff[i];
                break;
            }
        }
        // 如果没有找到正数
        if (pre == -1) pos_flag = false; // 不存在正数差

        int pos_max = 2; // 初始化目前子序列长度
        i++;
        while (i < diff.size()) {
            if (pre > 0 && diff[i] < 0) {
                // 如果前面的差大于0
                // 则寻找一个小于0的差值
                pos_max++;
                pre = diff[i];
            }

            if (pre < 0 && diff[i] > 0) {
                // 如果前面的差小于0
                // 则寻找一个大于0的差值
                pos_max++;
                pre = diff[i];
            }

            i++;
        }

        // 找到第一个负数
        pre = 1;
        i = 0;
        int neg_flag = true; // 是否存在负数
        for (; i < diff.size(); i++) {
            if (diff[i] < 0) {
                pre = diff[i];
                break;
            }
        }
        // 如果没有找到负数
        if (pre == 1) neg_flag = false;

        int neg_max = 2; // 初始化当前子序列长度
        i++;
        while (i < diff.size()) {
            if (pre < 0 && diff[i] > 0) {
                neg_max++;
                pre = diff[i];
            }

            if (pre > 0 && diff[i] < 0) {
                neg_max++;
                pre = diff[i];
            }

            i++;
        }

        // 如果即不存在正数也不存在负数
        if (!pos_flag && !neg_flag) return 1;
        // 如果只存在正数
        else if (pos_flag && !neg_flag) return 2;
        // 如果只存在负数
        else if (!pos_flag && neg_flag) return 2;
        else return max(pos_max, neg_max);
    }

    
};

时间复杂度O(n)；空间复杂度O(n)

思路3：动态规划

1.定义dp数组
如果要以下标为i的元素作为子序列的结尾，需要记录这个元素是波峰还是波谷。因此定义dp[i][0]表示[0, i]中以i作为波峰元素的最长摆动序列长度；dp[i][1]表示[0, i]中以i作为波谷元素的最长摆动子序列

2.递推公式：
考虑第i个元素，
dp[i][0]表示以第i个元素作为波谷，因此需要找到前面的某个波峰，接在后面作为波谷，因此dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中j遍历[0, i-1]，并且nums[j] > nums[i]
dp[i][1]表示以第i个元素作为波峰，因此需要找到前面的某个波谷，接在后面作为波峰，因此dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中j遍历[0, i-1]，并且nums[j] < nums[i]

3.初始化：
dp[0][0]和dp[0][1]表示以第一个元素作为波峰或者波谷，因此长度为1。对于每个元素来说，都可以以自己作为波峰或者波谷，因此都初始化为1。

4.遍历顺序：
从左到右

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        // 边界检查：要求至少1个元素
        int len = nums.size();
        if (len == 0) return 0;
        if (len == 1) return 1;

        // 定义dp数组
        vector<vector<int>> dp(len, vector<int>{1, 1});
        // 初始化
        dp[0][0] = dp[0][1] = 1;

        // 从左到右遍历
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) {
                    // 尝试以i元素作为波谷
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1);
                }

                if (nums[j] < nums[i]) {
                    // 尝试以i元素作为波峰
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1);
                }
            }
        }
        
        return max(dp[len - 1][0], dp[len - 1][1]);
    }
};

最大子序和

题目：53

思路1：暴力破解法：元素下标从第一个元素到最后一个元素，分为作为子序列起始元素，遍历起始元素后面的元素，记录最大子序列和。

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

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

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

我的理解：可以将整个序列看成是多个子序列，将多个子序列进行组合成一个更大的子序列，那么只有当子序列之和为正时合并才会使得组合而成的子序列的值变大。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int count = 0; // 表示一段连续的数组和

        for (int x : nums) {
            count += x; // 累积

            // 更新最大连续和
            result = max(result, count);

            // 如果这一段小于0那么就重新开始计算
            if (count < 0) count = 0;
        }

        return result;
    }
};

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

思路3：动态规划，因为是子数组问题，可以考虑使用动态规划解决原问题与子问题。

1.定义dp数组：
dp[i]表示[0, i]下标内以下标i结尾的最大的连续子数组和，这样暴力法中连续子数组的右端就被确定下来了。

2.确定递推公式：
要么dp[i - 1] + nums[i]，要么只能是nums[i]。
因此递推公式就是max(dp[i - 1] + nums[i], nums[i])

3.初始化：
dp[0]只能是第一个元素

4.遍历顺序：
从前向后

5.例子：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        // 边界检查：如果数组为空返回0
        if (len == 0) return 0;

        // 定义dp数组和初始化
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];

        int result = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = max(result, dp[i]);
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)，但是由于只依赖与前面一个元素，所以可以降到O(1)

总结

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

饼干分发：小饼干尽量满足胃口小的

最长摇摆序列：保持相邻两个元素波动，即删除单调坡度上的点

最大子序列和：将序列看成是多个子序列，只有子序列和为正才能参与组合，子序列和为负只会拉低组合序列的和的大小。

买卖股票的最佳时机II

题目：122

思路1：买入股票之后，只要股票价格在涨，就不卖出；当股票价格下跌时就立即卖出。

特殊情况是整个序列都是递增的，不会出现下降，这个时候需要判断是否为最后一个元素

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int in, out;
        in = prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i - 1] <= prices[i] && i != prices.size() - 1) {
                continue;
            } else if (prices[i - 1] <= prices[i] && i == prices.size() - 1) {
                profit += prices[i] - in;
                break;
            } else {
                out = prices[i - 1];
                profit += out - in;

                in = prices[i];
            }
        }

        return profit;
    }
};

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

思路2：贪心算法：如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？

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

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

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

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1])…..(prices[1] - prices[0])。

如图：

局部最优：收集每天的正利润，全局最优：求得最大利润。

局部最优可以推出全局最优，找不出反例，试一试贪心

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 范围检查：至少存在一个元素
        int len = prices.size();
        if (len == 0 || len == 1) return 0;
        
        int result = 0;
        for (int i = 1; i < len; i++) {
            int tmp = prices[i] - prices[i - 1];
            if (tmp > 0) result += tmp;
        }

        return result;
    }
};

贪心思路与思路1原理上是一样的，都是累积大于0的利润，思路1是累积一段，贪心是累积每一天。

思路3：动态规划：

1.定义dp数组：
每一天分为持有和不持有股票的状态，因此dp[i][0]表示第i天持有股票的最大利润；dp[i][1]表示第i天上不持有股票的最大利润

2.递推公式：
dp[i][0]：第i天持有股票，由于同时只能持有一个股票，所以要么前一天不持有股票， dp[i - 1][1] - prices[i];要么前一天也持有股票，dp[i][0] = dp[i - 1][1]；因此dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][1])
dp[i][1]：第i天不持有股票，那么要么前一天也不持有股票，dp[i-1][1]；要么前一天持有股票，然后今天卖出，dp[i-1][0] + prices[i]。因此dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

3.初始化：
第0天，持有股票为-prices[i]；不持有股票为0

4.遍历顺序：
从前向后

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 边界检查：至少一个元素
        if (prices.size() <= 1) return 0;

        // 定义dp数组
        vector<vector<int>> dp(prices.size(), vector<int>{0, 0});
        // 初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        // 遍历每一天
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }

        // 最后一定是不持有股票利润更高
        return dp[prices.size() - 1][1];
    }
};

时间复杂度O(n)；空间复杂度O(n)，因为每个元素只依赖于前者，所以可以优化至O(1)

跳跃游戏

题目：55

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

思路1：贪心算法
每次可以跳跃的最大距离是nums[i]，这表示下一步可以走的距离是[i+1, i+nums[i]]，如果nums[i]为0，表示永远不可能到达重点。
局部最优：跳跃到下一步最大距离最大的位置，这样下一次可供选择的跳跃点更多，这里注意应该是覆盖范围更大。
整体最优：所有的覆盖范围累加如果能够超越边界就可以跳出去。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 边界检查：如果只有一个元素切这个元素就是0
        if (nums.size() == 1) return true;

        int max_cover = 0;
        // 遍历每一步，记录最远到达范围
        int len = nums.size();
        for (int i = 0; i <= max_cover; i++) {
            max_cover = max(max_cover, i + nums[i]);
            if (max_cover >= len - 1) return true;
        }

        return  false;
    }
};

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

思路2：贪心

每次走下一步时，挑选可选范围中走的更远的一步

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        // 遍历每一步
        int cur_index = 0; // 当前下标
        while (cur_index < len) {
            int next_range = nums[cur_index]; // 下一步可选范围
            // 如果下一步可选范围为0
            if (next_range == 0) return false; // 表示下一步是死路
            if (cur_index + next_range >= len) return true;

            int next_index = INT_MIN; // 初始化下一步的下标
            for (int i = 1; i <= next_range; i++) {
                // 下一步走的最远
                int tmp = nums[cur_index + i] + cur_index + i;
                next_index = max(next_index, tmp);
            }

            cur_index = next_index;
        }

        return true;
    }
};

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

跳跃游戏II

题目：45

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

思路1：每一步尽可能的多走，但是不能有多远就跳多远，因为这样就不能确定下一步能够到达哪里。

注意覆盖范围内是一步可以跳到的，因此更新下一步的覆盖范围时也是尽可能使得下一步的覆盖范围达到最大。

总体思路是：计算当前可以到达的最大范围，这是一步可以到达的范围；那么然后比较这些范围内下一步可以到达的范围，选择下一步最大范围的跳，这样能够保证以最小步数来扩充范围。跳跃之后判断点是否超过终点，超过终点就结束。

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

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

如图：

从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。

这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

• 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
• 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

class Solution {
public:
    int jump(vector<int>& nums) {
        int cur_cover = 0; // 当前覆盖范围，一步内可达
        int next_cover = 0; // 下一步可到达范围
        int times = 0; // 次数
        // 边界检查：如果只有一个元素
        if (nums.size() == 1) return 0;

        for (int i = 0; i < nums.size(); i++) {
            next_cover = max(next_cover, i + nums[i]);

            // 当i已经走到当前覆盖范围的边界时
            if (i == cur_cover) {
                times++;
                cur_cover = next_cover; // 走下一步
                if (cur_cover >= nums.size() - 1) break;
            }
        }

        return times;
    }
};

时间复杂度O(n)，每个元素最多遍历一次；空间复杂度O(1)

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

题目：1005

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

思路1：
设负数个数为neg，则首先应该把负数变成正数才能使得和最大，所以整体思路为：
如果neg 大于等于 k：那么把所有的负数变成正数就可以；
如果neg 小于k：判断是否存在0：如果存在0，那么剩下的次数全变化0即可；否则接着判断剩下次数的奇偶：如果是偶数，那么可以将一个正数来回变化偶数次，不影响最后结果；如果是奇数，那么前面的偶数次可以用来做反复变化，最后一次将最小的正数变成负数即可。

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

局部最优可以推出全局最优。

真正实施代码：

int largestSumAfterKNegations(vector<int>& nums, int k) {
        // 升序排列
        sort(nums.begin(), nums.end());

        // 首先处理负数
        int i;
        for (i = 0; i < nums.size(); ++i) {
            if (k == 0) break; // 次数用完退出

            if (nums[i] < 0) {
                // 消耗一次变化次数
                --k;
                nums[i] = -nums[i];
            } else if (nums[i] == 0){
                k = 0;
                break; // 当遇到非负数时退出循环
            } else {
                break;
            }
        }

        // 此时K表示所有的负数都被消耗
        if (k > 0) {
            if (k % 2 == 0) {
                // 此时无需再处理数组
                ;
            } else {
                // 重新排序选择最小的整数取反即可
                sort(nums.begin(), nums.end());
                nums[0] = -nums[0];
            }
        }


        int ans = 0;
        for (int j = 0; j < nums.size(); ++j)
                ans += nums[j];

        return ans;
    }

时间复杂度O(nlogn)，即主要是排序消耗的时间；空间复杂度O(1)

优化思路：

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

这里优化了判断当负数处理完之后判断是否有0的存在，直接反复处理最小的元素即可。

贪心周总结

股票问题：把一段时间的利润拆分成这几天每一天的利润。即用一天价格减去前一天的价格做差。

这样贪心的思路就是：只收集正利润，即上涨的利润。全局最优：得到最大利润

跳跃游戏I：问题转换为覆盖范围，即每次跳跃取最大步数是这一步目前的最大覆盖范围。

局部最优：每次都取最大范围。

整体最优：整体最大覆盖范围是否能够到达终点。

跳跃游戏II：当前最大覆盖范围：一步内可以到达的地方。如果当前最大覆盖范围没有到达终点，那么就需要再走一步，扩大覆盖范围。新走的一步也要使得覆盖范围最大，即保证下一步的覆盖范围最大。即在当前覆盖范围内可走的下标 i + nums[i] 就是走到下一步 i 的覆盖范围。

K次取反之后最大化的数组和：局部最优：让绝对值最大的负数先变成正数。然后再让绝对值最小的正数变成负数。

加油站

题目：134

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

思路：

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

那么为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？

如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。

那有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？ 如图：

如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。

区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择其实位置了。

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

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int rest_sum = 0;   // 记录累积汽油-消耗
        int max_sum = 0; // 记录总的汽油-消耗
        int result = 0;

        // 遍历每一个区间
        for (int i = 0; i < gas.size(); i++) {
            rest_sum += gas[i] - cost[i];
            max_sum += gas[i] - cost[i];

            // 如果一段区间累积汽油-消耗小于0
            // 那么起点必定不可能在这段区间内 
            if (rest_sum < 0) {
                result = i + 1;
                rest_sum = 0;
            }
        }

        if (max_sum >= 0) return result;
        else return -1;
    }
};

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

分发糖果

题目：135

思路：初始化时每个孩子至少一个糖果。

从前向后遍历，当左孩子小于右孩子时，右孩子糖果等于左孩子糖果+1；（那么如果左孩子大于右孩子呢？理论上应该是左孩子糖果等于右孩子+1，但是遍历顺序是从前向后，所以此时没办法确定右孩子的糖果数目；如果令左孩子糖果书-1，那么会影响前边的遍历结果。）从左向右保证：相邻的两个孩子，如果右边的分数高，那么右边的糖果比左边多一个

接着从后向前遍历，此时就能够根据右孩子糖果数确定左孩子糖果数，此时如果左孩子大于右孩子，那么此时左孩子有两个选择，一个选择是右孩子+1，另一个选择是上一步中求得的这个孩子应该有的糖果数。应该选择较大的，这样既能保证大于左边又能保证大于右边。

时间复杂度O(n)，空间复杂度O(n)

采用了两次贪心的策略：

• 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。从左向右保证：相邻的两个孩子，如果右边的分数高，那么右边的糖果比左边多一个
• 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。从右向左保证，如果左边的分数高，左边的糖果比右边多一个

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int len = ratings.size();

        // 初始每个孩子至少一个糖果
        vector<int> need1(len, 1);
        vector<int> need2(len, 1);

        // 从左向右更新
        // 如果右边大于左边，则右边多分一个
        // 如果右边小于等于左边，不能做减法，即不能让左边少一个
        // 因为从左向右更新，意味着左边的都已经符合要求，如果令左边做减法，就不符合要求
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1])
                need1[i] = need1[i - 1] + 1;
        }

        // 从左向右保证：相邻的两个孩子，如果右边的分数高，那么右边的糖果比左边多一个
        // 但是没有保证：如果左边的分数高，左边的糖果比右边多一个
        // 所以需要从右向左更新
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1])
                need2[i] = need2[i + 1] + 1;
        }

        // 应该取较大值
        // 取较小值不能同时满足两个保证要求
        int result = 0;
        for (int i = 0; i < len; i++)
            result += max(need1[i], need2[i]);
        
        return result;
    }
};

柠檬水找零

题目：860

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

思路：

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

账单是20的情况，为什么要优先消耗一个10和一个5呢？

因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

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

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        // 使用哈希表保证每张美元个数
        unordered_map<int, int> map; // <面额, 个数>
        map[5] = 0;  // 5美元不需要找零
        map[10] = 0; // 10美元需要找零1张5美元
        map[20] = 0; // 20美元需要找零3张5美元、或者2张5美元加1张10美元

        // 遍历所有顾客
        for (int i = 0; i < bills.size(); i++) {
            switch (bills[i]) {
                case 5 : {
                    // 5美元不需要找零
                    map[5]++;
                    break;
                }
                case 10 : {
                    map[10]++;
                    // 找零5美元
                    if (map[5] == 0) return false;
                    map[5]--;
                    break;
                }
                case 20 : {
                    map[20]++;
                    // 优先尝试找零10美元
                    if (map[10] >= 1 && map[5] >= 1) {
                        map[10]--;
                        map[5]--;
                        break;
                    } else if (map[5] >= 3) {
                        map[5] -= 3;
                        break;
                    } else {
                        return false;
                    }
                }
                default : {
                    return false;
                }
            } // end switch
        } // end for

        return true;
    }
};

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

根据身高重建队列

题目：406

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

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

思路：

遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。

如果两个维度一起考虑一定会顾此失彼。

对于本题相信大家困惑的点是先确定k还是先确定h呢，也就是究竟先按h排序呢，还是先按照k排序呢？

如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。

那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面,，后续根据k值选择插入位置，防止小的k值还不存在就插入大的k值下标），让高个子在前面。

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

那么只需要按照k为下标重新插入队列就可以了，为什么呢？

以图中{5,2} 为例：

按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。

所以在按照身高从大到小排序后：

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

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

例子：

排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]

插入的过程：

• 插入[7,0]：[[7,0]]
• 插入[7,1]：[[7,0],[7,1]]
• 插入[6,1]：[[7,0],[6,1],[7,1]]
• 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
• 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
• 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

时间复杂度O(nlogn + n^2)，后面的时间复杂度是指遍历一遍所有的元素，然后根据k选择插入位置

空间复杂度O(n)

class Solution {
public:
    static bool MyCmp(const vector<int> &v1, const vector<int> &v2) {
        if (v1[0] > v2[0]) return true;
        else if (v1[0] == v2[0]) return v1[1] < v2[1]; // 如果身高相同则k值小的在前面
        else return false;
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 首先根据身高排序
        sort(people.begin(), people.end(), MyCmp);

        // 此时前面的身高均大于后面的
        // 并且都满足k的需求
        // 即使前面再被插入其它元素也不影响
        list<vector<int>> que; // list底层实现是链表，插入快
        for (int i = 0; i < people.size(); i++) {
            int k = people[i][1];

            // 找到第k个位置的迭代器
            auto it = que.begin();
            while (k--) ++it;
            que.insert(it, people[i]);
        }

        return vector<vector<int>>(que.begin(), que.end());
    }
};

贪心周总结

加油站：这道题首先想要能够走完一圈，每一站的加油量减去消耗量之和（就是总油量要大于总消耗量），走完一圈一定是正的。

其次是判断起点的问题，将每一站的差值从第0站开始进行累加，当累加为负数时，说明起始位置到这一站之间都不能作为起点，因为不管是哪一个作为起点，到这里都会却油。所以必须从后面一站开始。接着重新进行累加，继续更新。

贪心的思想体现在：累加的差值如果小于0，那么至少从下一个开始。

分发糖果：这个问题的关键在于：如果从左向右比，那么一定是根据前者才能更新后者，所以只能更新后者，更新后者的情况就是当后者评分大于前者时，此时后者应该比前者多1个。（为什么不能当前者评分大于后者时，更新前者为后者糖果数目+1呢？因为此时后者的糖果数并不是最终结果，如果在后续操作中后者糖果发生改变，那么这一步对于前者的修改就是不正确的。）

在从左向右比之后，此时所有后者大于前者的人都已经更新。

接着需要从右向左进行比较，此时可以根据后者更新前者，具体更新逻辑为，如果前者的评分大于后者，那么前者的糖果数应该取上一步更新的糖果数和后者+1中较大值。

贪心的思想体现在：从左向右：只要后者大于前者，那么后者就为前者+1；从右向左，如果前者大于后者，那么前者就必须比后者多。

买柠檬水找零：贪心的思想体现在，尽可能先使用10元进行找零，因为10元只能对于20元进行找零，而5元既可以对10元找零，也可以对20元找零。

根据身高重建队列：存在两个维度，应该先使得一个维度有序，然后再考虑另一个维度。

这里先按照身高从大到小排序（身高相同的话则k小的站前面），这样能够保证高个子在前面。

然后根据第二个维度k值，将其放入第k个下标对应的位置。

（为什么k小的站前面？主要是因为进行重新插入时，从前向后处理。如果先处理K大的，那么有可能对于一个队列来说超出目前队列的长度）

贪心体现在：k值表示前面正好有k个大于或者等于这个身高的人。那么已经按照身高排序，然后按照身高从高向低处理，插入到第k个位置，至少能够保证前面有k个人大于或等于该身高。即使后续前面再插入新元素，新元素一定是比该身高低。（因为后处理的元素比先处理的元素身高低）

用最少数量的箭引爆气球

题目：452

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

我的思路（存在缺陷）：对于一个气球来说，想要引爆的射箭位置就是[L, H]，那么如果想要一次引爆多个气球，就需要从他们的交集位置射出，所以我的思路就是遍历所有气球位置，使得尽量从交集位置射出。

但是问题是：气球顺序会影响两个位置范围结合求子集的顺序，这样会使得

[[3,9],[7,12],[3,8],[6,8],[9,10],[2,9],[0,9],[3,9],[0,6],[2,8]]

比如上面的气球顺序，当[7,12],[3,8]相遇，那么子集范围就确定为[7,8]，不能达到最小箭的数目

这里明显是6可以解决除了最后一个所有的气球，但是如果采用上面的思路，就需要3个箭头。

但是如果排序之后再使用上面算法，可以通过，但是时间复杂度是O(max(nlogn, n^2))

作者的思路：

局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，只要记录一下箭的数量就可以了。为了让气球尽可能的重叠，需要对数组进行排序。

如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）

class Solution {
public:
    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() == 0) return 0;
        sort(points.begin(), points.end()); // 根据左边界排序

        // 从第二个点开始遍历
        int ans = 1; // 假设总是存在第一个元素
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i- 1][1]) {
                // 第二个元素的左边界大于第一个元素右边界
                // 说明不挨着
                ans++; 
            } else {
                // 以最小右边界继续
                points[i][1] = min(points[i - 1][1], points[i][1]);
            }
        }

        return ans;
    }
};

时间复杂度O(nlogn)，快速排序；空间复杂度O(1)

无重叠区间

题目：435

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

思路：贪心：发现重叠的区间就移除较大的区间

与上一题一样，先进行排序，然后依次比较相邻两个区间：已知后者的左端点一定大于等于前者的左端点，如果后者的左端点大于等于前者的右端点，说明后者整体区间在前者后面，无重叠；否则说明存在交集，应该将右边界更大的删除，以更小的右边界作为切割点。

时间复杂度O(nlogn)，快速排序；空间复杂度O(1)

class Solution {
public:
    // 左边界从小到大
    // 如果左边界相同，则按照右边界从小到大
    static bool MyCmp(const vector<int> &v1, const vector<int> &v2) {
        if (v1[0] < v2[0]) return true;
        else if (v1[0] == v2[0]) return v1[1] < v2[1];
        else return false;
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 边界检查
        int len = intervals.size();
        if (len < 1) return 0;

        sort(intervals.begin(), intervals.end());

        int ans = 0; // 出现重叠的区间个数
        // 假设至少有一个元素
        for (int i = 1; i < len; i++) {
            if (intervals[i - 1][1] <= intervals[i][0]) {
                // 如果前一个区间的右边界小于后一个区间的左边界则不重叠
                continue;
            } else {
                // 出现重叠
                // 以较小的右边界作为新的，这样可以减少重叠
                ans++;
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            }
        }

        return ans;
    }
};

另一种思路：按照右边界排序，从左至右计算不重叠的区间个数，总区间个数减去不重叠的区间个数就是需要移除的区间个数。

这里记录非交叉区间的个数还是有技巧的，如图：

区间，1，2，3，4，5，6都按照右边界排好序。

当确定区间 1 和 区间2 重叠后，如何确定是否与 区间3 也重贴呢？

就是取 区间1 和 区间2 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。

接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘了已经是按照右边界排序的了。

区间4结束之后，再找到区间6，所以一共记录非交叉区间的个数是三个。

总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。

划分字母区间

题目：763

思路1：遍历所有元素，对于每一个元素求其最后一次出现的下标作为max_end，一个分区的长度以内部所有元素中最大的max_end作为分区右边界。

int FindMaxend(const string &s, char c) {
    // 返回c在s中最后一次出现的位置下标
    for (int i = s.size() - 1; i >= 0; --i) {
        if (s[i] == c) return i;
    }

    // c一定在s中，否则出错
    exit(-1);
}

vector<int> partitionLabels(string s) {
    if (s.size() == 0) return vector<int>(0);
    int max_end = 0; // 表示当前

    // 假设s不为空，初始化第一个字符的max_end
    max_end = FindMaxend(s, s[0]);
    int count = 1; // 初始化第一个分区的长度
    vector<int> ans;
    // 从第二个元素开始
    for (int i = 1; i < s.size(); ++i) {
        if (i <= max_end) {
            // 说明还在上一个分区内
            count++; // 分区长度加1
        } else {
            // 说明这是一个新的分区
            // 应该保留上一次的长度
            ans.push_back(count);

            count = 1; // 从这个新的元素开始计数
        }

        // 更新max_end
        max_end = max(max_end, FindMaxend(s, s[i]));
    }
    // 每一段的更新逻辑是遇到下一段才会更新
    // 最后一段不会遇到下一段，所以没有更新
    ans.push_back(count);

    return ans;
}

时间复杂度O(n^2)，遍历所有字符，每次在循环中查找当前字符出现的最后位置；空间复杂度O(n)。这里的n是进行函数调用栈的空间消耗

思路2：与上面基本一致，但是作者首先使用一个hash表计算出所有元素的最后一次的下标，这个时间复杂度为O(n)；

然后一个细节是当 i == max_end时就可以记录当前分区长度了，这样就不需要循环结束之再统计最后一个分区的长度

vector<int> partitionLabels(string s) {
    // 使用一个hash表记录每一个字母最后出现的位置
    // 题目中说明左右字母均是小写
    int hash_table[26] = {0};
    for (int i = 0; i < s.size(); ++i) 
        hash_table[s[i] - 'a'] = i;

    int count = 0;  // 记录每一个分区的长度
    int max_end = 0; // 每一个分区的最大右边界
    vector<int> ans;
    for (int i = 0; i < s.size(); ++i) {
        // 更新max_end右边界
        max_end = max(max_end, hash_table[s[i] - 'a']);
        count++;

        if (i == max_end) {
            // 当前字母就是同一分区最后一个元素
            // 记录该分区长度
            ans.push_back(count);

            // 长度归零
            count = 0;
        }
    }

    return ans;
}

时间复杂度O(n)；空间复杂度O(1)，固定hash表的长度

思路3：每个字符都有一个区间[start, end]，先按照左边界进行排序，然后求重叠区间的合并区间即可。

class Solution {
public:
    // 按照左边界升序排列
    static bool Cmp(const vector<int> &v1, const vector<int> &v2) {
        return v1[0] < v2[0];
    }

    vector<int> partitionLabels(string s) {
        // 找到每个字符出现的开始和结束区间
        unordered_map<char, vector<int>> map;
        for (int i = 0; i < s.length(); i++) {
            if (map.find(s[i]) == map.end()) {
                map[s[i]] = vector<int>{i, i}; // 记录起始和结束下标
            } else {
                map[s[i]][1] = i;
            }
        }

        // 保存所有区间
        vector<vector<int>> intervals;
        for (auto it = map.begin(); it != map.end(); ++it) {
            intervals.push_back(it->second);
        }
        sort(intervals.begin(), intervals.end());
        // 将重叠区间合并为更大的区间
        vector<int> result;
        result.push_back(intervals[0][1] - intervals[0][0] + 1);

        for (int i = 1; i < intervals.size(); i++) {
            // 如果发生重叠
            if (intervals[i][0] <= intervals[i - 1][1]) {
                // 合并区间
                intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
                intervals[i][0] = min(intervals[i][0], intervals[i - 1][0]);
                result.back() = intervals[i][1] - intervals[i][0] + 1;
            } else {
                // 没发生重叠记录新的区间大小
                result.push_back(intervals[i][1] - intervals[i][0] + 1);
            }
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)

合并区间

题目：56

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

思路：这道题与“用最少的数量的箭引爆气球”和”无重叠区间“类似，都是先排序使得左右边界中的一个边界有序，然后根据另一个边界判断是否出现重叠。

这道题出现重叠时需要将以更小的左边界和更大的右边界合并两个区间。

以左边界排序，然后根据右边界的情况判断是否重叠：已知排序之后前者的左边界 小于等于 后者的左边界，如果后者的左边界大于（注意这里等于也是重叠）前者的右边界，说明后者整体在前者的后面，无重叠现象，此时不需要处理；否则，就应该以前者的左边界作为新区间的左边界，以max(前者的右边界, 后者的右边界)作为新区间的右边界。

时间复杂度O(nlogn)，快速排序的时间；空间复杂度O(n)，需要一个ans数组

class Solution {
public:
    static bool Cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0];
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 边界检查：至少一个元素
        int len = intervals.size();
        if (len == 0) return vector<vector<int>>();

        sort(intervals.begin(), intervals.end(), Cmp); // 左边界升序排列

        vector<vector<int>> result;
        result.push_back(intervals[0]);
        for (int i = 1; i < len; i++) {
            if (result.back()[1] >= intervals[i][0]) {
                // 如果发生重叠
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                // 如果不发生重叠
                result.push_back(intervals[i]);
            }
        }

        return result;
    }
};

作者的思路：与上面基本一致，不一样的是一点细节：作者直接把第一个区间加入答案中，当发现重叠时，就直接在答案的最后一个区间上进行修改；无重叠的话就直接把当前区间加入答案数组。等待更新

而我的思路是比较连续两个区间，如果出现重叠区间，就把合并后的区间赋给后者，然后继续参与比较；只有当遇到不重叠时，才把前者加入答案（也就是之前几个区间合并后的结果）。这样做的坏处就是最后一个区间需要在循环结束之后再添加。

贪心周总结

用最少的箭引爆气球、无重叠区间、合并区间：这三道题都类似，第一步就是先使得一个维度有序，这里采用的都是使得左边界从小到大排列；然后从前到后根据比较相邻两个区间的右边界判断是否出现重叠；最后根据重叠与否做出不同的行为。

划分字母区间：尽量保证一个分区的右边界为区间内元素最后一次出现的位置。另外可以表示出每个字符的左右边界，合并边界区间。

这道题给我的收获是：如果在处理一个循环时需要根据原始数据进行某些操作，考虑是否可以提前进行这些操作。

也就是在n循环中做时间复杂度为n的操作，可以优化为先做时间复杂度为n的操作得到需要的数据，然后再进行n循环。

单调递增的数字

题目：738

思路：贪心的思路：一旦出现了非单调递增的情况，即strNum[i - 1] > strNum[i]，那么最接近的单调递增整数应该是令strNum[i - 1]–，令strNum[i]以及后面的数字全都等于9.

从前向后遍历还是从后向前遍历：

（1）从前向后遍历：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。

采用两次遍历的方法：第一次遍历从前向后，如果单调递增，则不做处理；如果出现非递增情况，令前一位减去1，后面所有位置为9。

由于减去1之后有可能会使得小于更前面的数字，因此需要第二次遍历，从后向前遍历，当前位置数字如果小于前面的，应该使得当前数字为9，另前一位数字减去1.

使用两个栈，一个栈保存源数据，一个栈保存结果数据。

时间复杂度O(n)，包括使用栈保存每一位数字、遍历栈中每一位数字求存储结果每一位的栈、遍历结果栈得到最终答案；

空间复杂度O(n)

(2)从后向前遍历：只要前者大于后者，就令后者以及后面全都为9，前者减去1

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string origin = to_string(n);
        int len = origin.length();
        int index = len; // 从这个位置之后全都应该为9
        for (int i = len - 2; i >= 0; i--) {
            if ((origin[i] - '0') > (origin[i + 1] - '0')) {
                // 如果前者更大
                origin[i]--;
                index = i + 1;
            }
        }
        // 令flag以及后面全部为9
        for (int i = index; i < len; i++)
            origin[i] = '9';
        
        return atoi(origin.c_str());
    }
};

时间复杂度O(n)；空间复杂度O(n-)

监控二叉树

题目：968

思路：摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。

所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。

为什么不从头结点开始看起呢，为啥要从叶子节点看呢？

因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。

所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

所以确定采用后续遍历。

接着是计算摄像头个数：递归的处理就是返回结点的状态。

分别有三个数字来表示结点状态：

• 0：该节点无覆盖
• 1：本节点有摄像头
• 2：本节点有覆盖

因为在遍历树的过程中，就会遇到空节点，那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？

回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。

那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。

所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

主要有如下四类情况：

• 情况1：左右节点都有覆盖

左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。

• 情况2：左右节点至少有一个无覆盖的情况

如果是以下情况，则中间节点（父节点）应该放摄像头：

• left == 0 && right == 0 左右节点无覆盖
• left == 1 && right == 0 左节点有摄像头，右节点无覆盖
• left == 0 && right == 1 左节点有无覆盖，右节点摄像头
• left == 0 && right == 2 左节点无覆盖，右节点覆盖
• left == 2 && right == 0 左节点覆盖，右节点无覆盖

这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。

此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。

• 情况3：左右节点至少有一个有摄像头

如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）

• left == 1 && right == 2 左节点有摄像头，右节点有覆盖

• left == 2 && right == 1 左节点有覆盖，右节点有摄像头

• left == 1 && right == 1 左右节点都有摄像头

• 情况4：头结点没有覆盖

以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况。

时间复杂度O(n)

空间复杂度O(n)，递归栈消耗时间

思路2：贪心：一个摄像头可以覆盖上中下三层，放在中间覆盖范围最大。尽量让叶子节点的父节点安装摄像头

采用后序遍历处理：如果头节点不妨也就省下一个，如果叶子不放省下指数级别。

使用3种状态表示结点：

• val的值为0表示未被监控
• 1表示已经被监控
• 2表示此位置放置监控。放置监控的位置本身表示被监控

1.递归的参数和返回值：参数是当前子树根节点，和父节点；返回值是左右字数监控个数

2.递归的终止：遇到空结点

3.处理逻辑：首先递归左右孩子。接着：如果当前结点是叶子结点，则在父亲结点安装监控，并令当前结点的状态为1.返回0

最后：根据当前状态和左右孩子状态处理：详细参考代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // val的值为0表示未被监控
    // 1表示已经被监控
    // 2表示此位置放置监控。放置监控的位置本身表示被监控
    int PostTraversal(TreeNode *cur, TreeNode *parent) {
        // 终止条件是遇到空结点
        if (cur == nullptr) return 0;

        // 递归左右孩子并放置监控
        int left = PostTraversal(cur->left, cur); // 左子树监控数
        int right = PostTraversal(cur->right, cur); // 右子树监控数

        // 处理当前结点
        if (cur->left == nullptr && cur->right == nullptr) {
            // 当前结点是叶子结点时
            parent->val = 2; // 在父亲结点放置监控
            cur->val = 1;
            return 0; // 返回当前子树的监控数字
        } 

        // 根据当前节点的状态
        if (cur->val == 2) {
            // 如果当前结点被放置了监控
            // 尝试覆盖父亲结点
            parent->val = max(parent->val, 1);
            return left + right + 1;
        } else if (cur->val == 1) {
            // 如果当前结点处于监控范围
            return left + right;
        } else {
            // 如果当前结点没有被监控
            // 在父节点放置监控
            parent->val = 2;
            cur->val = 1;
            return left + right;
        }
    }

    int minCameraCover(TreeNode* root) {
        // 边界检查：
        if (root == nullptr) return 0;

        int left = PostTraversal(root->left, root);
        int right = PostTraversal(root->right, root);

        // 处理左右孩子都为空
        if (left + right == 0) return 1;

        if (root->val == 2 || root->val == 0) return left + right + 1;
        else return left + right;
    }
};

（这里给出思考过程：如果空结点不进入递归，那么分四种情况：

1.当前结点没有孩子，即叶子结点：此时应该令父节点安装监控为状态2，当前结点为状态1，返回0；

2.当前结点只有左孩子：递归左子树得到左子树监控数目，然后根据当前结点的状态做处理（3种情况）；

3.当前结点只有右孩子：同理

4.当前结点有左右孩子：此时需要递归左右子树获得监控数目，然后再根据当前结点状态做处理

2、3、4这些情况代码重复，因此选择令空结点进入递归，并且返回0，这样就能使用left和right接收左右子树监控数目。