-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path135.candy.cpp
More file actions
58 lines (53 loc) · 1.62 KB
/
135.candy.cpp
File metadata and controls
58 lines (53 loc) · 1.62 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// Tag: Greedy, Array
// Time: O(N)
// Space: O(N)
// Ref: -
// Note: -
// Video: https://youtu.be/hvZxZWBUza8
// There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
// 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.
//
// Return the minimum number of candies you need to have to distribute the candies to the children.
//
// Example 1:
//
// Input: ratings = [1,0,2]
// Output: 5
// Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
//
// Example 2:
//
// Input: ratings = [1,2,2]
// Output: 4
// Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
// The third child gets 1 candy because it satisfies the above two conditions.
//
//
// Constraints:
//
// n == ratings.length
// 1 <= n <= 2 * 104
// 0 <= ratings[i] <= 2 * 104
//
//
class Solution {
public:
int candy(vector<int>& ratings) {
int size = ratings.size();
vector<int> candies(size, 1);
for (int i = 1; i < size; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (int i = size - 1; i > 0; i--) {
if (ratings[i] < ratings[i - 1]) {
candies[i - 1] = max(candies[i - 1], candies[i] + 1);
}
}
return accumulate(candies.begin(), candies.end(), 0);
}
};