文章目录

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?

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
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,并且,不得用于商业用途。如您有任何疑问或者授权方面的协商,请给我留言

文章目录