Leetcode(135) Candy

发表于 | 分类于

Description

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:

1
2
3
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:

1
2
3
4
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.

解法

网上看到的思路：先从左往右扫描一遍, 如果后面一个比前面大, 那么他分配的就多一颗糖, 否则就是1. 但是这样会产生一种情况, 就是两个相邻的排名一样, 那么后一个还是分一个, 但是后面的可能比这个值小, 但是仍然分得和这个值一样的糖, 因此还要从右往左再扫描一遍来补偿小的值.

具体代码如下：

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
class Solution {
    public int candy(int[] ratings) {
        if(ratings == null){
            return 0;
        }
        int[] res = new int[ratings.length];
        res[0] = 1;
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]){
                res[i] = res[i-1] + 1;
            }
            else{
                res[i] = 1;
            }
        }
        for(int i = ratings.length - 2; i >= 0 ; i--){
            if(ratings[i] > ratings[i+1] && res[i] <= res[i+1]){
                res[i] = res[i+1] + 1;
            }
        }
        int result = 0;
        for(int i = 0; i < ratings.length; i++){
            result += res[i];
        }
        return result;
    }
}