[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. 书影博客