Children are standing in a line to receive candy. Each child must receive at least one candy, and each child has a rating. Children with higher ratings must have more candy than their neighbors.
What is the minimum number of candies needed?
Simulate in order: assume the first child gets one candy. If the next child has a lower rating, the next child gets one fewer, and the previous child’s count increases by one. We need to track how many children before each child have consecutively higher ratings.
If the next child has a higher rating, they get one more candy than the previous child. Simulate accordingly. However, I got Wrong Answer many times T_T.
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
53
54
| class Solution {
public:
int candy(vector<int> &ratings) {
int len = ratings.size();
if(len == 0 || len == 1)return len;
vector<int>bigger(ratings.size(),0);
int count = 1;
int now = 1;
int max = 0;
int i;
for(i = 1;i < ratings.size();i++) {
if(ratings[i] > ratings[i-1]) {
if(max != 0) {
if(bigger[i-1] < max-1) {
count += max-1 - bigger[i-1];
}
}
max = 0;
bigger[i] = 0;
now += 1;
count += now;
}
else
if(ratings[i] < ratings[i-1]) {
bigger[i] = bigger[i-1] + 1;
if(now == 1) {
count += bigger[i] + now;
}
else {
max = now;
now = 1;
count += bigger[i] + now - (max-1);
}
}
else {
if(max != 0) {
if(bigger[i-1] < max-1) {
count += max-1 - bigger[i-1];
}
}
max = 0;
bigger[i] = 0;
now = 1;
count += 1;
}
}
if(max != 0) {
if(bigger[i-1] < max-1) {
count += max-1 - bigger[i-1];
}
}
return count;
}
};
|