LC135. 分糖果 candy
LC135. 分糖果 candy
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子中，评分更高的那个会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
n == ratings.length
1 <= n <= 2 * 10^4
0 <= ratings[i] <= 2 * 10^4
v1-左右扫描
理解题意
这种相邻依赖的题目，我们要看一下是否是只依赖一边。
比如分析下面几个场景：
单调上升的评分：[1,2,3,4] — 你会怎么分？总数是多少？
单调下降的评分：[4,3,2,1] — 你会怎么分？总数是多少？
有一个“峰”：[1,2,3,2,1] — 试着分配，观察中间的孩子需要多少糖果？
思考
可以发现，其实是依赖左右两边的。
那么先思考几个问题：
1）如果你从左到右“尽量少地”分配（每次只在需要时给当前孩子比左边多 1），能保证什么？能保证哪些相邻关系？
2）从右往左呢？
3）最后结果应该如何取舍？
思路
初始：给每个孩子 1 个糖果（数组
candies全为 1）。从左到右遍历（i 从 1 到 n-1）：
- 如果
rating[i] > rating[i-1]，就把candies[i] = candies[i-1] + 1； - 否则保持
candies[i]为当前值（也就是 1）。
记下最终的candies数组（这是“左→右”分配）。
- 如果
从右到左遍历（i 从 n-2 到 0）：
- 如果
rating[i] > rating[i+1]，就把另一个数组candiesR[i] = candiesR[i+1] + 1； - 否则保持
candiesR[i]为 1。
记下最终的candiesR数组（这是“右→左”分配）。
- 如果
注意：现在只做这两个单向分配并把数组写出来，不要合并它们（合并是下一步要讨论的内容）。
最后其实就是取二者的最大值，因为要同时满足左右两边。
实现
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
// 从左到右 看递增
int[] ltr = new int[n];
Arrays.fill(ltr, 1);
for(int i = 1; i < n; i++) {
if(ratings[i] > ratings[i-1]) {
ltr[i] = ltr[i-1]+1;
}
}
// 从右到左 看递减
int[] rtl = new int[n];
Arrays.fill(rtl, 1);
for(int i = n-2; i >= 0; i--) {
if(ratings[i] > ratings[i+1]) {
rtl[i] = rtl[i+1]+1;
}
}
//二者的最大值作为结果
int res = 0;
for(int i = 0; i < n; i++) {
res += Math.max(ltr[i], rtl[i]);
}
return res;
}
}效果
2ms 击败 99.31%
反思
如果「左边的状态」会影响当前，但「右边的状态」也可能有另一种独立影响，那就很可能要分别从两个方向处理。
小结
类似的题目其实还是不少的。
| 题目 | 为什么双向扫描 |
|---|---|
| LC135 Candy | 要同时满足左、右的“评分高→糖果多” |
| LC42 Trapping Rain Water | 每格水高度由左右最高墙共同决定 |
| LC84 Largest Rectangle in Histogram | 每个柱子的最大宽度取决于左右边界 |
| LC739 Daily Temperatures | 每天温度要看右边第一个更高温度的位置 |
| LC238 Product of Array Except Self | 每个位置要看左积和右积 |
开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~