[LeetCode]135. Candy | 分糖果

题目来源:LeetCode: 135 Candy

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?

  • 规则1:每个人手中至少一个
  • 规则2:评分更高的孩子比左右邻居糖果数量多:分别遍历比较比左侧孩子多,比右侧孩子多。
  • 贪婪算法(Greedy Algorithm),从左到右遍历确保高分孩子比左侧糖果多,从右向左遍历确保高分孩子比右侧糖果多。

时间复杂度:O(n), 空间复杂度O(1)

算法步骤

  1. 每个孩子一个糖果
  2. 从左到右遍历,ratings[i+1]>ratings[i]时,candies[i+1]=candies[i] +1
  3. 从右到左遍历,ratings[i-1]>ratings[i]时, candies[i-1]=max(candies[i-1], candies[i]+1)

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int candy(int* ratings, int ratingsSize) {
int *cadies = (int *)malloc(sizeof(int)*ratingsSize);
cadies[0] = 1;
for(int i=0; i<ratingsSize-1; i++){
if(ratings[i+1]>ratings[i])
cadies[i+1] = cadies[i] + 1;
else
cadies[i+1] = 1;
}
for(int i=ratingsSize-1; i>0; i--)
if(ratings[i-1]>ratings[i])
cadies[i-1] = cadies[i-1]>(cadies[i]+1)?cadies[i-1]:(cadies[i]+1);
int sum = 0;
for(int i=0; i<ratingsSize; i++)
sum += cadies[i];
return sum;
}

运行结果

28 / 28 test cases passed.
Status: Accepted
Runtime: 16 ms
Submitted: 0 minutes ago

You are here! Your runtime beats 20% of csubmissions.

总结

  1. 贪婪算法模拟现实世界操作中一种可行方案
  2. 该问题中多次顺序遍历,但时间复杂度认为O(n)
  3. 注意边界情况的处理

参考文献

  1. 书影博客