峰谷类问题的贪心分析：山峰、山谷、上坡、下坡、平原

摘要: 数组中与峰谷相关的概念

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们以分发糖果问题详细阐述一下峰谷类问题的分析过程。对于峰谷类问题，可以把数组视为一个山脉，我们要分析山脉上的山峰、山谷、上坡、下坡、平原等形态。

在分析峰谷类问题时，对当前点的判断与左右两边都有关系，左右两侧均有大于小于等于三种情况，综合起来共有 9 种，需要画图辅助理解。

在文章 峰谷类问题分类汇总 中总结了常见的峰谷类问题，可以参考。

---

$1 题目

• 135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

提示：

n == ratings.length
1 <= n <= 2e4
0 <= ratings[i] <= 2e4

示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

$2 题解

算法：贪心

将评分画在图上，可以得到一个类似波形图的图像。

图像整体可以视为一系列山峰。按照第一条要求，山谷的糖果数为 1。然后按照第二条要求，从各个谷向外扩展，每扩展一步，糖果数 +1。

这里对于山谷的定义是对于 nums[i]，如果 nums[i - 1], nums[i + 1] 均不小于 nums[i]，则 nums[i] 是谷。

按照以上定义，谷有 8 中形态，如图：

类似地，山峰有 5 中形态，此外上坡、下坡各有一种形态，如图。如果一个点是峰，则它必是上坡或下坡其中之一，或者既是上坡又是下坡。

对于一个位置，如果它是上坡，则左边的糖果数对该位置有影响，如果它是下坡，则右边的糖果数对它有影响。

• 是上坡而不是下坡，该位置糖果数为左侧的糖果数 +1。
• 是下坡而不是上坡，该位置糖果数为右侧的糖果数 +1。
• 既是上坡又是下坡，该位置糖果数为左侧糖果数和右侧的糖果数较大值 + 1。

关键的问题就是如何找到各个谷。以及找到各个谷后如何向两边扩展。

首先初始化答案数组为 1。

从左向右遍历一遍，枚举到 i 时：

• 若 nums[i - 1] < nums[i]，则 i 位置为上坡，糖果数为 i - 1 位置糖果数 + 1。
• 若 nums[i - 1] >= nums[i]，则 i 位置不是上坡，i - 1 的糖果数对 i 无影响，跳过。

然后从右向左遍历一遍，枚举到 i 时：

• 若 nums[i] > nums[i + 1]，则 i 位置为下坡，糖果数为 i + 1 位置糖果数 + 1。
• 若 nums[i] <= nums[i + 1]，则 i 位置不是下坡，i + 1 的糖果数对 i 无影响，跳过。

以上算法有一个冲突，就是当一个点既是上坡又是下坡时，该点的糖果数需要在两次遍历的结果中取较大值。

代码(C++)

class Solution {
public:
    int candy(vector<int>& ratings) {
        if(ratings.empty()) return 0;
        int n = ratings.size();
        if(n == 1) return 1;
        vector<int> candys(n, 1);
        for(int i = 1; i < n; ++i)
        {
            if(ratings[i - 1] < ratings[i])
                candys[i] = candys[i - 1] + 1;
        }
        for(int i = n - 2; i >= 0; --i)
        {
            if(ratings[i] > ratings[i + 1])
                candys[i] = max(candys[i], candys[i + 1] + 1);
        }
        int result = 0;
        for(int i: candys) result += i;
        return result;
    }
};

优化

从前面贪心的过程看，本题的难点有两个：

1. 从左向右遍历的时候，下坡的长度不知道，需要反向遍历完之后了才知道。
2. 峰的值要看左右两边的上坡下坡有多长。

为了解决这个问题，从左到有遍历时用变量 up 记录上坡的长度，down 记录下坡的长度。

当遇到谷底的时候，就表明一座山遍历结束了，那么我们只需要比较 up 和 down 的大小就知道峰顶取值了。

在从左到右遍历，计算当前山的 up 和 down 时，对谷和峰的判定各有两种情况：

1. 谷

• 前一个时刻 i - 1 在下降，当前时刻 i 上升了, i - 1 是前后两个山的谷。
• 前一个时刻 i - 1 在下降，当前时刻 i 不变，i - 1 是前一山的谷。
• 前一个时刻 i - 1 不变，当前时刻 i 上升了，i - 1 是后一山的谷。

2. 峰

• 前一个时刻 i - 1 在上升，当前时刻 i 下降了，i - 1 是前一山的峰。
• 前一个时刻 i - 1 在上升，当前时刻 i 不变，这种情况下，当前山只有上坡，没有下坡，i - 1 是前一山的峰。
• 前一个时刻 i - 1 不变，当前时刻 i 下降了，这种情况下，当前山只有下坡，没有上坡，i - 1 是后一山的峰。

此外，还有一种情况需要特殊处理，就是平原的情况。

3. 平原

• 前一个时刻 i - 1 不变，当前时刻 i 仍然不变，这种情况下，当前山没有下坡，也没有上坡，只有一个谷，i - 1 是谷。

一座山的糖果数可以写成三部分之和，$1 + \cdots + n$ 可以预处理：

1. 上坡：$1 + 2 + \cdots + up$。
2. 下坡：$1 + 2 + \cdots + down$。
3. 峰: $1 + max(up, down)$。

当出现某个点是前后山共用的山谷时，需要单独记录。

代码(C++)

class Solution {
public:
    int candy(vector<int>& ratings) {
        int result = 0;
        int n = ratings.size();
        int i = 0, public_valley = 0;
        while(i < n)
        {
            int j = i + 1;
            // 确定波峰，up, down 代表坡长度，均包含波峰点，因此长度至少为 1
            while(j < n && ratings[j - 1] < ratings[j])
                ++j;
            int peak = j;
            int up = j - i;
            // 确定波谷
            while(j < n && ratings[j - 1] > ratings[j])
                ++j;
            int down = j - peak + 1;
            if(up < down)
                swap(up, down);
            // 计算这一趟波峰波谷需要的糖果数量，波峰的糖果数量与上坡下坡较长的长度有关
            // 因此将波峰归到最长的一个坡
            // 已处理成 up >= down
            result += (up * (up + 1) / 2 + (down - 1) * down / 2);

            // 准备下一个波峰波谷
            // 如果是一段平的，即不存在坡，则 ++i，否则波谷会被下一个波峰波谷公用为起点，
            // 所以会在下一次的分配中再次被分配一个糖果，记录下公用的波谷数量
            if(j == i + 1)
                ++i;
            else
            {
                i = j - 1;
                public_valley += 1;
            }
        }
        return result - public_valley;
    }
};

---