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

  |  

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

  • 通过贪心策略将问题抽象成山脉上找峰谷的问题
  • 对当前点的判断与左右两边都有关系,左右两侧均有大于小于等于三种情况,综合起来共有 9 种,需要画图辅助理解
  • 峰谷类问题分类汇总

$1 题目

题目链接

135. 分发糖果

题目描述

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

    1. 每个孩子至少分配到 1 个糖果。
    1. 相邻的孩子中,评分高的孩子必须获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

样例

示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

$2 题解

算法1 — 贪心

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

图像像是一个山峰,按照第一条要求,谷底的糖果数为 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],则 i 位置不是下坡,i + 1 的糖果数对 i 无影响,跳过

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

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 的过程看,本题的难点有两个

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

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

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

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

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

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

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

一座山的糖果数可以写成三部分之和,1 + … + n 可以预处理

  1. 上坡:$1 + 2 + … + up$
  2. 下坡:$1 + 2 + … + down
  3. 峰: $1 + max(up, down)$

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

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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;
}
};

$3 扩展:峰谷类题目列表

峰谷类问题分类汇总


Share