LeetCode-Candy

文章目录

LeetCode地址：https://leetcode.com/problems/candy/

Problem:
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 n=ratings.length;
        if(n<2) return n;

        int[] maxseq=new int[n];
        for(int i=n-2; i>=0; --i)
            if(ratings[i]>ratings[i+1]) maxseq[i]=1+maxseq[i+1];

        int[] candies=new int[n];
        
        int sum=0;
        for(int i=0; i<n; ++i){
            candies[i]=1;
            
            if(i!=0 && ratings[i]>ratings[i-1])
            {
                candies[i]=1+Math.max(candies[i-1], maxseq[i]);
            }else{
                candies[i]+=maxseq[i];
            }
            
            sum+=candies[i];
        }
        return sum;
    }
}

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。