目录

零、前言

一、简单问题

455. 分发饼干

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

860. 柠檬水找零

二、序列问题

376. 摆动序列[*]

 738. 单调递增的数字

三、股票问题

122. 买卖股票的最佳时机 II

714. 买卖股票的最佳时机含手续费[*]

四、两个维度权衡问题

135. 分发糖果[*]

零、前言

贪心算法使用原则：手动模拟一下，若可以通过局部最优推出整体最优，而且想不到反例，那么就试一试贪心

贪心算法一般步骤：

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

一、简单问题

455. 分发饼干

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

小饼干先满足胃口小的孩子/大饼干先满足胃口大的孩子均可。

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

int largestSumAfterKNegations(vector& nums, int k) {
        // 尽可能把所有负数变成正数
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0) {
                if (k > 0) {
                    nums[i] = -nums[i];
                    k--;
                }
            }
        }
        // 此时若k>0，数组一定全为正数，只需处理k为奇数的情况
        sort(nums.begin(), nums.end());
        if (k > 0 && k % 2 != 0) {
            nums[0] = -nums[0];
        }
        return accumulate(nums.begin(), nums.end(), 0);
    }

本题采用贪心思想，尽可能把所有负数变为正数。若执行该操作后k仍然大于0，只需处理k为奇数的情况，取反最小的元素即可。

860. 柠檬水找零

bool lemonadeChange(vector& bills) {
        int fiveCnt = 0;
        int tenCnt = 0;
        for (auto i : bills) {
            if (i == 5)  fiveCnt++;
            else if (i == 10) {
                if (fiveCnt < 1)   return false;
                fiveCnt--;
                tenCnt++;
            }
            else {
                // 优先给出10元
                if (fiveCnt >= 1 && tenCnt >= 1) {
                    fiveCnt--;
                    tenCnt--;
                }
                else if (fiveCnt >= 3) {
                    fiveCnt -= 3;
                }
                else   return false;
            }
        }
        return true;
    }

本题较简单，分别处理三种情况即可。其中20元找零时用到了贪心思想。

---

二、序列问题

376. 摆动序列[*]

int wiggleMaxLength(vector& nums) {
        // 仅有一个元素或者含两个不等元素的序列也视作摆动序列
        if (nums.size() <= 1)    return nums.size();
        int deltaOld = 0;
        // 统计数组的峰值数量(默认开始有一个峰值)
        int res = 1;
        for (int i = 1; i < nums.size(); i++) {
            int deltaNew = nums[i] - nums[i - 1];
            if ((deltaOld <= 0 && deltaNew > 0) || (deltaOld >= 0 && deltaNew < 0)) {
                res++;
                deltaOld = deltaNew;
            }
        }
        return res;
    }

 如上图所示（来源：代码随想录），本题只需要统计数组中的峰值数量即可，即：前一个差值≤0，后一个差值＞0或前一个差值≥0，后一个差值＜0。

如下图所示（来源：代码随想录），注意其中的“=”符号，这样的情况也应被合法收入结果。

 738. 单调递增的数字

int monotoneIncreasingDigits(int n) {
        if (n < 10)  return n;
        string strNum = to_string(n);
        int index = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i]) {
                index = i;
                strNum[i - 1]--;
            }
        }
        for (int j = index; j < strNum.size(); j++) {
            strNum[j] = '9';
        }
        return stoi(strNum);
    }

本题有两个技巧：

• 邻位数字比较大小，可以转化为字符串进行操作，而不需要额外开辟数组储存每位数字；
• 从右向左进行操作。贪心体现在结果字符串strNum直接等于原数字（尽可能大），从右向左操作，若前一位减一后小于前前一位，也可以继续迭代修改数字。

本题若采用从左向右循环的方式代码如下：

if (n < 10)    return n;
        // 贪心，尽可能取对应数位上的最大值
        string strNum = to_string(n);
        for (int i = 1; i < strNum.size(); i++) {
            // 若不满足，前一位减一，后续位置全部置9
            if (strNum[i - 1] > strNum[i]) {
                int index = i;
                for (int j = index + 1; j < strNum.size(); j++) {
                    strNum[j] = '9';
                }
                while (index - 1 >= 0 && strNum[index - 1] > strNum[index]) {
                    strNum[index] = '9';
                    strNum[index - 1]--;
                    index--;
                }
                break;
            }
        }
        return stoi(strNum);

出现不满足条件的元素，就可以直接退出循环，减少循环次数。

---

三、股票问题

122. 买卖股票的最佳时机 II

int maxProfit(vector& prices) {
        int res = 0;
        for (int i = 0; i < prices.size() - 1; i++) {
            int delta = prices[i + 1] - prices[i];
            if (delta > 0)     res += delta;
        }
        return res;
    }

贪心思想，收集每天的正利润即可。

714. 买卖股票的最佳时机含手续费[*]

int maxProfit(vector& prices, int fee) {
        int res = 0;
        // 记录最低价格
        int min = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            // 1.低值时买入
            if (prices[i] < min)    min = prices[i];
            // 2.没有盈利时不操作
            if (prices[i] - min <= fee)    continue;
            // 3.盈利时计算利润（可能计算多次，但会更新最大利润）
            if (prices[i] - min > fee) {
                res += prices[i] - min - fee;
                // 若后续继续盈利，再进行该循环时会扣除上次操作的手续费（res += prices[i+1] - prices[i]）
                // 若后续不盈利，不影响最小值被更新[看成新的一天，新的序列]
                min = prices[i] - fee;
            }
        }
        return res;
    }

本题对于股票的操作存在三种情况：

• 情况一：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最低价格；
• 情况二：没有盈利，但也不是最低价格。不作操作，保持原有状态；
• 情况三：减去手续费后仍是递增数列，后面要继续收获利润。

情况三代码较难理解，可以把记录了累加结果后的数列看成新的数列，但第一个元素减去了手续费。后序序列的操作不受前面的影响：若第一个元素仍为min，继续循环即可，且得到的res差值不会累计手续费；若第一个元素非min，min会被更新。

---

四、两个维度权衡问题

135. 分发糖果[*]

int candy(vector& ratings) {
        vector res(ratings.size(), 1);
        // 处理右边比左边大的情况
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1])   res[i] = res[i - 1] + 1;
        }
        // 处理左边比右边大的情况
        for (int j = ratings.size() - 2; j >= 0; j--) {
            if (ratings[j] > ratings[j + 1]) {
                res[j] = max(res[j + 1] + 1, res[j]);
            }
        }
        return accumulate(res.begin(), res.end(), 0);
    }

本题采用两次贪心的策略：

• 先从左到右遍历，处理右边孩子评分比左边大的情况；
• 再从右到左遍历，处理左边孩子评分比右边大的情况。

该过程如下图所示（来源：代码随想录）：

 尤其注意第二次贪心时有两种选择：一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。