-
Notifications
You must be signed in to change notification settings - Fork 95
/
candy.cpp
52 lines (50 loc) · 1.7 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
48
49
50
51
52
/*****************************************
Solution 1: traditional one-pass method
*****************************************/
class Solution {
public:
int candy(vector<int> &ratings) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if(ratings.empty())
return 0;
int res = 1, cur = 1, st = 0, stnum = 1;
for(int i = 1; i < ratings.size(); ++i) {
if(ratings[i] > ratings[i-1]) {
st = i;
stnum = ++cur;
} else if(ratings[i] < ratings[i-1]) {
cur = 1;
res += (i-st)<stnum?(i-st-1):(i-st);
} else {
st = i;
stnum = cur = 1;
}
res += cur;
}
return res;
}
};//from fanfank@github.com
/****************************************
Solution 2: a smart two-pass solution
****************************************/
class Solution {
public:
int candy(vector<int> &ratings) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int ret = 0;
if (ratings.size() == 0)
return ret;
vector<int> dp(ratings.size(), 1);
for (int i = 1; i < ratings.size(); i++)
if (ratings[i] > ratings[i - 1])
dp[i] = dp[i - 1] + 1;
ret = dp[ratings.size() - 1];
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
dp[i] = max(dp[i], dp[i + 1] + 1);
}
ret += dp[i];
}
return ret;
}
};//from iphkwan@github.com