题目描述
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Example 1:
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
题意:老师想给孩子们分发糖果,有 N
个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。你需要按照以下要求,帮助老师给这些孩子分发糖果:每个孩子至少分配到 1 个糖果,相邻的孩子中,评分高的孩子必须获得更多的糖果。那么这样下来,老师至少需要准备多少颗糖果呢?
算法1
(两次遍历) $O(n)$
题解1:我们分两次来考虑这个问题,我们使用两个数组分别表示仅考虑左边的孩子和仅考虑右边的孩子的结果。
首先给每个人都发一颗糖果,然后从左往右遍历,如果当前人表现大于左边孩子表现,那么f[i] = f[i - 1] + 1
。
同样给每个人都发一颗糖果,然后从右往左遍历,如果当前人表现大于右边孩子表现,那么g[i] = g[i + 1] + 1
。
为了满足上述条件,每个孩子应该发的糖果就是max(f[i],g[i])
;
我们同样可以使用一个数组来优化,并且在第二趟遍历的时候就记录答案,不进行第三次遍历来优化。
int candy(vector<int>& ratings) {
int n = ratings.size(),res = 0;
if(n < 2) return n;
vector<int> f(n,1),g(n,1);
for(int i = 1 ; i < n ; i ++)
if(ratings[i] > ratings[i - 1])
f[i] = f[i - 1] + 1;
for(int i = n - 2 ; i >= 0 ; i --)
if(ratings[i] > ratings[i + 1])
g[i] = g[i + 1] + 1;
for(int i = 0 ; i < n ; i ++)
res += max(f[i],g[i]);
return res;
}
算法2
(一次遍历不使用额外空间) $O(n)$
题解2:上述做法最优解是使用一个数组,遍历两遍数组,我们同样可以不使用额外空间,仅遍历一次就得到最优解。其实我们可以将每个孩子的表现化成一个折线图,那么我们可以发现在上升过程中,肯定分配的糖果个数是[1,2,3,..k]
,如果是下降过程中肯定是[t,t-1,...,1]
这样的趋势才能获得最小值。那么我们把整个走势图划分成若干个先上升再下降的山,那么不考虑山顶元素上山过程就是[1,2,..,k]
,下山就是[t,t-1,...,2,1]
,那么山顶就是max(k + t) + 1
。不管在上山过程中还是下山过程中遇到了平地(ratings[i] == ratings[i - 1]
),那么我们认为这座山已经提前结束。
根据上述思想,我们使用up,down
两个变量分别代表上山的高度和下山的高度,old_state
代表上一个状态,1
代表在上山,0代表在平地,-1代表在下山。接下来我们考虑什么时候山已经结束了:
- 连续两个平地(连续三个孩子的
rating
值相等),那么只需要给中间孩子分配一个糖果就可以了res ++
。 - 上山过程中遇到了平地,那我们只需要从上山第一个位置分配一个,然后依次递增到山顶就可以了,这个时候因为
rating[i - 1]
是上一个山的山顶同时不会作为下一个山的起点,不会发生重复计算。 - 下山过程中遇到了平地,那我们只需要从两边山脚分配一个,然后依次递增到山顶,山顶分配的是
max(up,down) + 1
。这个时候因为rating[i - 1]
是上一个山的山脚同时不会作为下一个山的起点,不会发生重复计算。 - 下山过程中遇到了上山,那我们只需要从两边山脚分配一个,然后依次递增到山顶,山顶分配的是
max(up,down) + 1
。这个时候因为rating[i - 1]
是上一个山的山脚同时作为下一个山的起点,发生重复计算我们需要减去 1。
遍历完整个数组之后,将最后一座山的值加入答案。
class Solution{
public:
inline int count(int n){return n * (n + 1) / 2;}
int candy(vector<int>& ratings)
{
int n = ratings.size();
if(n < 2) return n;
int res = 0,up = 0,down = 0,old_state = 0;
for(int i = 1 ; i < n ; i ++)
{
int new_state = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
if(new_state == 0 && old_state == 0) res ++;
else if(new_state == 0 && old_state > 0)
{
res += count(up) + up + 1;
up = 0,down = 0;
}
else if(new_state == 0 && old_state < 0)
{
res += count(up) + count(down) + max(up,down) + 1;
up = 0,down = 0;
}else if(new_state > 0 && old_state < 0)
{
res += count(up) + count(down) + max(up,down) + 1 - 1;
up = 0,down = 0;
}
if(new_state > 0) up ++;
else if(new_state < 0) down ++;
old_state = new_state;
}
res += count(up) + count(down) + max(up,down) + 1;
return res;
}
}
很多同学看到官方题解可能不太好理解,因为官方题解直接将四种情况都直接合并了。
情况1:直接res ++
情况2:因为上山过程中遇到了平地,这个时候down = 0
,山顶其实要加上up + 1
,官方题解将up
和1分开来加了。
情况3:因为下山过程中遇到了平地,这个时候山顶要加上max(up,down) + 1
,官方题解同样将max(up,down)
和1分开来加了。
情况4:下山过程中遇到了上山,这个时候山顶要加上max(up,down) + 1
,但因为第一座山的右山脚是第二座山的左山脚会重复计算所以要减去1,所以就加上max(up,down)
就可以了。
综上我们可以发现,只要遇到了平地就直接加上1(情况1,2,3bu hui chu),如果不是连续的平地导致山的结束(情况2,3,4),就加上count(up) + count(down) + max(up,down)
并重置up,down
,如果是情况1,up,down
已经在上一次平地被重置了,无需重置。所以代码可以优化为如下。
class Solution {
public:
inline int count(int n){return n * (n + 1) / 2;}
int candy(vector<int>& ratings) {
int n = ratings.size();
if(n < 2) return n;
int res = 0,up = 0,down = 0,old_state = 0;
for(int i = 1 ; i < n ; i ++)
{
int new_state = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
if((old_state > 0 && new_state == 0) || (old_state < 0 && new_state >= 0))
{
res += count(up) + count(down) + max(up,down);
up = 0,down = 0;
}
if(new_state > 0) up ++;
if(new_state < 0) down ++;
if(new_state == 0) res ++;
old_state = new_state;
}
res += count(up) + count(down) + max(up,down) + 1;
return res;
}
};
666