1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 12, 2014
4+ Problem: Candy
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/candy/
7+ Notes:
8+ There are N children standing in a line. Each child is assigned a rating value.
9+ You are giving candies to these children subjected to the following requirements:
10+ - Each child must have at least one candy.
11+ - Children with a higher rating get more candies than their neighbors.
12+ What is the minimum candies you must give?
13+
14+ Solution: You may refer to https://github.com/AnnieKim/ITint5/blob/master/031_%E5%88%86%E9%85%8D%E7%B3%96%E6%9E%9C.cpp
15+ 1. O(n) space.
16+ 2. traverse only once with O(1) space.
17+ */
18+
19+ public class Solution {
20+ public int candy (int []ratings ) {
21+ return candy_1 (ratings );
22+ }
23+ public int candy_1 (int []ratings ) {
24+ int N =ratings .length ;
25+ if (N ==0 )return 0 ;
26+ int []height =new int [N ];
27+ int res =0 ;
28+ height [0 ] =1 ;
29+ for (int i =1 ;i <N ; ++i ) {
30+ height [i ] =1 ;
31+ if (ratings [i ] >ratings [i -1 ]) {
32+ height [i ] =height [i -1 ] +1 ;
33+ }
34+ }
35+ for (int i =N -2 ;i >=0 ; --i ) {
36+ if (ratings [i ] >ratings [i +1 ]) {
37+ height [i ] =Math .max (height [i ],height [i +1 ] +1 );
38+ }
39+ }
40+ for (int i =0 ;i <N ; ++i ) {
41+ res +=height [i ];
42+ }
43+ return res ;
44+ }
45+ public int candy_2 (int []ratings ) {
46+ int N =ratings .length ;
47+ if (N ==0 )return 0 ;
48+ int candy =1 ,res =1 ;
49+ int maxVal =1 ,maxIdx =0 ;
50+ for (int i =1 ;i <N ; ++i ) {
51+ if (ratings [i ] >=ratings [i -1 ]) {
52+ candy =ratings [i ] ==ratings [i -1 ] ?1 :candy +1 ;
53+ maxVal =candy ;
54+ maxIdx =i ;
55+ }else {
56+ if (candy ==1 ) {
57+ if (maxVal <=i -maxIdx ) {
58+ ++maxVal ;
59+ ++res ;
60+ }
61+ res +=i -maxIdx -1 ;
62+ }
63+ candy =1 ;
64+ }
65+ res +=candy ;
66+ }
67+ return res ;
68+ }
69+ }
