【LeetCode】135. Candy
LeetCode 135
2023-09-11 14:20:27 时间
Candy
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?
左右各遍历一次,依据前一个位置的candy数计算当前位置需要的最小candy数(最少为1)
由于两次遍历的结果都要满足,因此对同一位置取max即可。
class Solution { public: int candy(vector<int>& ratings) { if(ratings.empty()) return 0; int n = ratings.size(); vector<int> left(n, 1); for(int i = 1; i < n; i ++) { if(ratings[i] > ratings[i-1]) left[i] = left[i-1] + 1; } vector<int> right(n, 1); int sum = max(left[n-1], right[n-1]); for(int i = n-2; i >= 0; i --) { if(ratings[i] > ratings[i+1]) right[i] = right[i+1] + 1; sum += max(left[i], right[i]); } return sum; } };
相关文章
- Leetcode: Remove K Digits
- Leetcode: Encode and Decode Strings
- JS Leetcode 80. 删除有序数组中的重复项 II题解,常规解法与快慢双指针做法
- JS leetcode 有序数组的平方 题解分析,灵活运用Math.pow与Math.abs方法
- [LeetCode] Distinct Subsequences
- [LeetCode] Construct Binary Tree from Inorder and Postorder Traversal
- 129、【动态规划/贪心算法】leetcode ——53. 最大子数组和(C++版本)
- [LeetCode] 1048. Longest String Chain 最长字符串链
- [LeetCode] 774. Minimize Max Distance to Gas Station 最小化去加油站的最大距离
- [LeetCode] Strange Printer 奇怪的打印机
- [LeetCode] 568. Maximum Vacation Days 最大化休假日
- [LeetCode] Minimum Height Trees 最小高度树
- leetcode 409 Longest Palindrome 最长回文串(简单)