FilesExpand file tree

 master

/

Candy.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

50 lines (43 loc) · 1.36 KB

 master

/

Candy.java

Copy path

Top

File metadata and controls

• Code
• Blame

50 lines (43 loc) · 1.36 KB

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

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

import java.util.Arrays;

public class Candy {

public int candy(int[] ratings) {

int[] left = new int[ratings.length];

int[] right = new int[ratings.length];

Arrays.fill(left, 1);

Arrays.fill(right, 1);

for (int i = 1; i < ratings.length; i++) {

if (ratings[i] > ratings[i - 1]) {

left[i] = left[i - 1] + 1;

}

}

for (int i = ratings.length - 2; i >= 0; i--) {

if (ratings[i] > ratings[i + 1]) {

right[i] = right[i + 1] + 1;

}

}

int sum = 0;

for (int i = 0; i < ratings.length; i++) {

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

}

return sum;

}

/**

* 在上面的基础上优化了一下，去掉了一个数组

*/

public int candy2(int[] ratings) {

int[] candys = new int[ratings.length];

Arrays.fill(candys, 1);

for (int i = 1; i < ratings.length; i++) {

if (ratings[i] > ratings[i - 1]) {

candys[i] = candys[i - 1] + 1;

}

}

int sum = candys[ratings.length - 1], prev = 1;

for (int i = ratings.length - 2; i >= 0; i--) {

int cur = ratings[i] > ratings[i + 1] ? prev + 1 : 1;

sum += Math.max(cur, candys[i]);

prev = cur;

}

return sum;

}

}