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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Solution {
    public int candy(int[] ratings) {
        int[] count = new int[ratings.length];
        Arrays.fill(count, 1);
        for (int i = 1; i < ratings.length; i++){
            if (ratings[i] > ratings[i-1]){
                count[i] = count[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 2; i >=0; i--){
            if (ratings[i] > ratings[i + 1]){
                count[i] = Math.max(count[i], count[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int c : count){
            sum += c;
        }
        return sum;
    }
}