Candy, Leetcode 解题笔记

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?



public class Solution {
    public int candy(int[] ratings) {
        int[] num = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            num[i] = 1;
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]){
                num[i] = num[i-1]+1;
        for(int i = ratings.length-2; i >= 0; i--){
            if(ratings[i] > ratings[i+1] && num[i] <= num[i+1]){
                num[i] = num[i+1]+1;
        int sum = 0;
        for(int i = 0; i < num.length; i++){
            sum += num[i];
        return sum;

这种两边扫描的方法是一种比较常用的技巧,LeetCode中Trapping Rain Water和这道题都用到了,可以把这种方法作为自己思路的一部分,通常是要求的变量跟左右元素有关系的题目会用到哈。


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s