-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCandy.cc
More file actions
43 lines (33 loc) · 1.04 KB
/
Candy.cc
File metadata and controls
43 lines (33 loc) · 1.04 KB
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
#include <vector>
namespace Candy {
class Solution {
public:
int candy(std::vector<int> &ratings) {
if (ratings.empty()) {
return 0;
}
if (ratings.size() == 1) {
return 1;
}
// initialize an all 1 vector
std::vector<int> candies(ratings.size(), 1);
// scan from left to right
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) {
}
}
// scan from right to left
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
}
}
// sum up
int sum = 0;
for (int i = 0; i < candies.size(); i++) {
sum += candies[i];
}
return sum;
}
};
}