-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCandy.cpp
More file actions
39 lines (33 loc) · 1.03 KB
/
Candy.cpp
File metadata and controls
39 lines (33 loc) · 1.03 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
/**
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
*/
class Solution {
public:
int candy(vector<int> &ratings) {
vector<int> lc(ratings.size(),1);
vector<int> rc(ratings.size(),1);
int res=0;
//scan from left to right
for (int i=1;i<lc.size();i++){
if (ratings[i]>ratings[i-1]){
lc[i]=lc[i-1]+1;
}
}
//scan from right to left
for (int i=rc.size()-2;i>=0;i--){
if (ratings[i]>ratings[i+1]){
rc[i]=rc[i+1]+1;
}
}
//get result
//note that we get the max of lc and rc
for (int i=0;i<ratings.size();i++){
res+=max(lc[i],rc[i]);
}
return res;
}
};