-
Notifications
You must be signed in to change notification settings - Fork 0
/
candy.cpp
47 lines (38 loc) · 1.04 KB
/
candy.cpp
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
/**
* Greey algorithm
* Time: O(n)
* Space: O(n)
* Author: Teddy
* Date: 29-01-2015
*/
/**
* two round traversal, asscending order and descending order
* 1 2 3 2 1 4 5 8 1 4 9 2
*/
class Solution {
public:
int candy(vector<int> &ratings) {
int len = ratings.size();
if(len <= 0){
return 0;
}
int total = 0;
vector<int> candies(len, 0);
candies[0] = 1;
total++;
// assending order traversal
for(int i = 1; i < len; i++){
candies[i] = ratings[i] > ratings[i - 1] ? candies[i - 1] + 1 : 1;
total += candies[i];
}
// descending order traversal
for(int i = len - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]){
int increasement = candies[i + 1] - candies[i] + 1;
candies[i] += increasement;
total += increasement;
}
}
return total;
}
};