分发糖果——使用贪心算法

server/2024/9/24 15:18:09/

135. 分发糖果

已解答

困难

相关标签

相关企业

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求,给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。

示例 1:

输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2:

输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。

提示:

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

这个算法不太容易想到,我一开始是两边都照顾,导致无法正确地执行这个算法。但是,看了解析了才明白,贪心在先从前往后,然后在从后往前

要考虑的情况:

1.当前孩子的评分与前一个孩子的评分比较,以确定是否应该增加当前孩子的糖果数量。
2.当前孩子的评分与后一个孩子的评分比较,以确定是否应该增加当前孩子的糖果数量。

因此,先从前往后,然后在从后往前看。

执行用时分布

3ms

击败99.88%使用 C++ 的用户

消耗内存分布

19.68MB

击败35.53%使用 C++ 的用户

11ms21ms32ms42ms53ms63ms74ms0%5%10%15%

11ms21ms32ms42ms53ms63ms74ms

代码C++

class Solution {
public:int candy(vector<int>& ratings) {int sum =0;int size =ratings.size();vector<int> vec(size, 1); for(int i =1;i<size;i++){if(ratings[i-1]<ratings[i]){vec[i]=vec[i-1]+1;}}for(int k =size-2;k>=0;k--){if(ratings[k]>ratings[k+1]){vec[k] = max(vec[k],vec[k+1]+1);}}for(auto it : vec){sum += it;}return sum;}
};

http://www.ppmy.cn/server/20938.html

相关文章

2024LarkXR新增功能系列之二 | 普通应用多开推流

在数字化迅速演变的今天&#xff0c;3D数字时代的到来已经改变了许多行业的运作方式。特别是在虚拟现实领域&#xff0c;实时云渲染技术正迅速成为关键驱动力&#xff0c;这种技术使得复杂的3D视觉内容可以迅速、高效地通过云平台渲染并传输到用户的设备上&#xff0c;无论设备…

opencv绘制线段------c++

绘制线段 bool opencvTool::drawLines(std::string image_p, std::vector<cv::Point> points) {cv::Mat ima cv::imread(image_p.c_str()); // 读取图像&#xff0c;替换为你的图片路径 cv::Scalar red cv::Scalar(0, 0, 255); // Red color int thickness 2;// 遍…

R语言高级数据管理

一&#xff0c;数学函数 绝对值函数abs(x) sqrt(x) 开平方根 不小于某个数的最小整数ceiling(x) 不大于某个数的最大整数floor(x) 四舍五入round(x) sin(x) cos(x) log(x) 二&#xff0c;统计函数 求平均值 > x<-c(2,3,4,5,6,7,8,9,10) > mean(x) 求和 &g…

未来已来:解锁AGI的无限潜能与挑战

未来已来&#xff1a;解锁AGI的无限潜能与挑战 引言 假设你有一天醒来&#xff0c;发现你的智能手机不仅提醒你今天的日程&#xff0c;还把你昨晚做的那个奇怪的梦解释了一番&#xff0c;并建议你可能需要减少咖啡摄入量——这不是科幻电影的情节&#xff0c;而是人工通用智能…

Scala Extention

正则 import scala.util.matching.Regex import scala.util.matching.Regex.Match/*----------------------------------------------------------匹配 */ val rtr "^(\\w)([a-z0-9]{2,})\\.(com|cn|edu|org)$"; val regex:Regex rtr.r // 同 Java 的简单匹配 val…

【LeetCode刷题记录】94. 二叉树的中序遍历

94 二叉树的中序遍历 给定一个二叉树的根节点 root &#xff0c;返回 它的 中序 遍历 。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,3,2] 示例 2&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[] 示例 3&#xff1a; 输入&…

今日早报 每日精选15条新闻简报 每天一分钟 知晓天下事 4月28日,星期日

每天一分钟&#xff0c;知晓天下事&#xff01; 2024年4月28日 星期日 农历三月二十 1、 五一假期高速免费通行&#xff0c;预测峰值日出现在5月3日。 2、 财政部、民政部下达2024年中央财政困难群众救助补助资金超1546亿元。 3、 全国总工会拟授予1088人全国五一劳动奖章&am…

使用Python实现语音识别与处理模型

语音识别与处理是一项重要的人工智能技术&#xff0c;它可以将人类语音转换成文本形式&#xff0c;从而实现语音命令识别、语音转写等功能。在本文中&#xff0c;我们将介绍语音识别与处理的基本原理和常见的实现方法&#xff0c;并使用Python来实现这些模型。 什么是语音识别…