FilesExpand file tree

 master

/

Candy.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

32 lines (28 loc) · 870 Bytes

 master

/

Candy.java

Copy path

Top

File metadata and controls

• Code
• Blame

32 lines (28 loc) · 870 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

28

29

30

31

32

/**

* Practiced on 10/6/2013

*

* 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?

*/

package com.congli.leetcode;

public class Candy {

public int candy(int[] ratings) {

int size = ratings.length;

int[] left = new int[size];

int[] right = new int[size];

for (int i = 1; i < size; ++i) {

left[i] = ratings[i] > ratings[i-1] ? left[i-1]+1 : 0;

right[size-i-1] = ratings[size-i-1] > ratings[size-i] ? right[size-i]+1 : 0;

}

int total = 0;

for (int i = 0; i < size; ++i) {

total += Math.max(left[i], right[i]);

}

return total + size;

}

}