Leetcode: Candy
2023-09-11 14:14:08 时间
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?
贪心法
复杂度
时间 O(N) 空间 O(N)
思路
典型的贪心法,如果一个孩子比另一个孩子的分高,我们只多给1块糖。我们可以先从左往右遍历,确保每个孩子根他左边的孩子相比,如果分高,则糖要多1个,如果分比左边低,就只给一颗。然后我们再从右往左遍历,确保每个孩子跟他右边的孩子相比,如果分高则糖至少多1个(这里至少多1个的意思是,我们要取当前孩子手里糖的数量,和其右边孩子糖的数量加1,两者的较大值)。
1 public class Solution { 2 public int candy(int[] ratings) { 3 if(ratings.length <= 1){ 4 return ratings.length; 5 } 6 int[] candies = new int[ratings.length]; 7 candies[0] = 1; 8 // 先从左往右分糖,分数较高的多拿一颗糖,分数较少的只拿一颗糖 9 for(int i = 1; i < ratings.length; i++){ 10 if(ratings[i] > ratings[i - 1]){ 11 candies[i] = candies[i - 1] + 1; 12 } else { 13 candies[i] = 1; 14 } 15 } 16 int sum = candies[candies.length - 1]; 17 // 再从右往左继续分糖,分数较高的确保比右边多一颗就行了 18 for(int i = ratings.length - 2; i >= 0; i--){ 19 if(ratings[i] > ratings[i + 1]){ 20 candies[i] = Math.max(candies[i + 1] + 1, candies[i]); 21 } 22 sum += candies[i]; 23 } 24 return sum; 25 } 26 }
相关文章
- Java实现 LeetCode 676 实现一个魔法字典(暴力)
- Java实现 LeetCode 668 乘法表中第k小的数(二分)
- Java实现 LeetCode 395 至少有K个重复字符的最长子串
- Java实现 LeetCode 241 为运算表达式设计优先级
- 【刷题】【LeetCode】000-十大经典排序算法
- leetcode - 子数组最大平均值
- LeetCode(21):合并两个有序链表
- LeetCode-1604. 警告一小时内使用相同员工卡大于等于三次的人【哈希表,排序,数组】
- leetcode 576. 出界的路径数
- [leetcode]第1题
- 【LeetCode 简单 数组 python3】27. 移除元素
- [LeetCode] 95. 不同的二叉搜索树 II ☆☆☆(递归,n个数组成的所有二叉搜索树)
- 【Leetcode刷题Python】1143. 最长公共子序列