Problem
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?
Example 1:
Input: [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: [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.
Solution: Greedy
First pass: left to right, the right one will have one more candy than the left one if taller.
Second pass: right to left, the left one will be at least one more candy than the right one if taller.
Time Complexity: O(n)
Space Complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int candy(vector<int>& ratings) { const int n = ratings.size(); vector<int> ans(n, 1); for (int i = 1; i < n; ++i) if (ratings[i] > ratings[i - 1]) ans[i] = ans[i - 1] + 1; for (int i = n - 2; i >= 0; --i) if (ratings[i] > ratings[i + 1]) ans[i] = max(ans[i], ans[i + 1] + 1); return accumulate(begin(ans), end(ans), 0); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment