【LeetCode】分发糖果
2024-08-24 16:47:59
【问题】老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
你需要按照以下要求,帮助老师给这些孩子分发糖果:
每个孩子至少分配到 1 个糖果。
相邻的孩子中,评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?
示例 :
输入: [,,]
输出:
解释: 你可以分别给这三个孩子分发 、、 颗糖果。
示例 :
输入: [,,]
输出:
解释: 你可以分别给这三个孩子分发 、、 颗糖果。
第三个孩子只得到 颗糖果,这已满足上述两个条件。
解题思路:
【思路】首先我们对整个数组进行初始化为1,dp[n]中元素都为1,第一次从左向右进行遍历,如果右边的得分大于左边的得分,则右边分得的糖果数比坐边多一个,不能贪多哟!但是我们并没有更新左边得分大于右边得分的情况,因此需要第二次遍历!
第二次遍历从右向左,类似于第一次,当ratings[i]>ratings[i+1]的同时,还要满足dp[i]<=dp[i+1],为什么要多一个条件呢?这是因为第一次遍历确定了部分糖果数的正确大小关系,第二次遍历不能更改,加上这个条件后,我们只更新第一次遍历错误的糖果数!
C++代码:时间复杂度O(2*n)=O(n)
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
if(n < )
return n;
vector<int> dp(n, );
for(int i = ;i < n; i++){
if(ratings[i-] < ratings[i]){
dp[i] = dp[i-] + ;
}
}
for(int i = n-; i >= ; i--){
if(ratings[i] > ratings[i+] && dp[i] <= dp[i+]){
dp[i] = dp[i+] + ;
}
}
int sum = ;
for(int i: dp){
sum += i;
}
return sum;
}
};
最新文章
- 【bzoj3124】 Sdoi2013—直径
- 利用Aspose.Pdf将扫描的电子书修改为适合在kindle上查看
- wince和window mobile winphone
- 笔记本PS/2键盘无法使用,试下这个方法
- Linux下实现视频读取(二)---camera參数设定
- 蜗牛—JSONJ学习ava转变
- 201521123106《java程序设计》第一周学习总结
- buttongroup中content一次性加载的解决方法
- centos/linux下的安装Nginx
- log4j日志输出性能优化-缓存、异步
- Python学习之路基础篇--10Python基础,函数进阶
- Android GreenDao使用教程
- js处理时间时区问题
- Mac安装HomeBridge适配小米Homekit报错:module未找到解决
- SWUST OJ (943)
- 第十届蓝桥杯JavaB组总结
- Work at a KFC fast food restaurant
- PAT 甲级 1083 List Grades
- 【摘自lvs官网】lvs介绍
- 「Codeforces Round #441」 Classroom Watch