分发糖果(力扣135)

news/2025/2/23 12:49:36

题目说相邻的两个孩子中评分更高的孩子获得的糖果更多,表示我们既要考虑到跟左边的孩子比较,也要考虑右边的孩子,但是我们如果两边一起考虑一定会顾此失彼。这里就引入一个思想:先满足右边大于左边时的糖果分发情况,再满足左边大于右边时的糖果分发情况。需要注意的是,在满足后者的情况时,我们用到贪心的思想:取candyVec[i + 1] + 1 (满足后者情况时的糖果数量)和 candyVec[i] (满足前者情况时得到的糖果数量)中较大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。大家可以结合下面的代码及注释理解此题。

代码及注释如下:

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy(ratings.size(),1);
        //先满足右边大于左边时的糖果分发情况
        for(int i = 1;i < ratings.size();i++){
             if(ratings[i] > ratings[i - 1]){
                candy[i] = candy[i - 1] + 1;
             } 
        }
        //再满足左边大于右边时的糖果分发情况
        for(int i = ratings.size() - 2;i >= 0;i--){
            if(ratings[i] > ratings[i + 1]){
        //取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,
        //保证第i个小孩的糖果数量既大于左边的也大于右边的
                candy[i] = max(candy[i],candy[i + 1] + 1);
            }
        }
        int sum = 0;
        for(int i = 0;i < candy.size();i++){
            sum += candy[i];
        }
        return sum;
    }
};


http://www.niftyadmin.cn/n/5863412.html

相关文章

贪心算法

int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题 为一个小老鼠准备了M磅的猫粮&#xff0c;准备去和看守仓库的猫做交易&#xff0c;因为仓库里有小老鼠喜欢吃的五香豆&#xff0c;第i个房间有J[i] 磅的五香豆&#xf…

【HeadFirst系列之HeadFirstJava】第3天之从零开始理解Java中的主数据类型和引用

从零开始理解Java中的主数据类型和引用 《Head First Java》是一本非常适合初学者的Java入门书籍&#xff0c;它以轻松幽默的方式讲解了Java的核心概念。在第三章节中&#xff0c;书中详细介绍了Java的主数据类型&#xff08;Primitive Types&#xff09;和引用&#xff08;Re…

SpringBoot中实现限流和熔断功能

我们将使用Java的ScheduledExecutorService来实现一个简单的令牌桶算法(Token Bucket Algorithm),并结合一个自定义的服务类来处理第三方API调用。 1. 创建限流器 首先,创建一个简单的限流器类: import java.util.concurrent.*;public class SimpleRateLimiter {

计算机专业知识【数据库完整性约束:数据质量的坚固防线】

在数据库管理的领域中&#xff0c;数据的准确性、一致性和可靠性是至关重要的。为了保障这些特性&#xff0c;我们引入了各种完整性约束机制。接下来&#xff0c;就为大家详细介绍用户定义的完整性约束、实体完整性约束、参照完整性约束和关键字完整性约束&#xff0c;让数据库…

利用爬虫获取淘宝商品描述:实战案例指南

在电商领域&#xff0c;商品描述是消费者了解产品细节、做出购买决策的重要依据。精准获取淘宝商品描述不仅能帮助商家优化产品信息&#xff0c;还能为市场研究和数据分析提供丰富的数据资源。本文将详细介绍如何利用爬虫技术精准获取淘宝商品描述&#xff0c;并分享关键技术和…

2012年IMO几何预选题第6题

设有非等腰的 △ A B C \triangle ABC △ABC, O O O 和 I I I 分别为外心和内心. 在边 A C AC AC, A B AB AB 上分别存在两点 E E E 和 F F F, 使得 C D C E A B CDCEAB CDCEAB, B F B D A C BFBDAC BFBDAC. 设 ( B D F ) (BDF) (BDF) 和 ( C D E ) (CDE) (CDE)…

sklearn中的决策树

sklearn 中的决策树 关键概念、核心问题 节点 根节点&#xff1a;没有进边&#xff0c;有出边。包含最初的&#xff0c;针对特征的提问。中间节点&#xff1a;既有进边也有出边&#xff0c;进边只有一条&#xff0c;出边可以有很多条。都是针对特征的提问。叶子节点&#xff1…

mysql之规则优化器RBO

文章目录 MySQL 基于规则的优化 (RBO)&#xff1a;RBO 的核心思想&#xff1a;模式匹配与规则应用RBO 的主要优化规则查询重写 (Query Rewrite) / 查询转换 (Query Transformation)子查询优化 (Subquery Optimization) - RBO 的重中之重非相关子查询 (Non-Correlated Subquery)…