当前位置: 首页 > article >正文

贪心算法解决分发糖果问题

代码随想录链接:代码随想录

思路:

由于每个孩子都要得到一块糖果,因此初始化一个全为1的数组,该数组的长度等于孩子的个数

从前往后遍历,如果位置i处的孩子对应的分数大于位置i-1处的孩子的分数,令该孩子获得的糖果数量为位置i-1处孩子获得的糖果数量+1

从后往前遍历数组中的每个元素,如果位置i处的孩子对应的分数大于位置i+1处的孩子的分数,令该孩子获得的糖果数量为位置i+1处孩子糖果数量+1原先该孩子获得的糖果数量最大值

两次遍历结束后,统计数组中的每个元素之和,即表示获得的最终结果

代码:

class Solution {
    /**
         分两个阶段
         1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 1
         2、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大
    */
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyVec = new int[len];
        candyVec[0] = 1;
        for (int i = 1; i < len; i++) {
            candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
        }

        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int num : candyVec) {
            ans += num;
        }
        return ans;
    }
}

http://www.kler.cn/a/448202.html

相关文章:

  • Spring Boot 多数据源解决方案:dynamic-datasource-spring-boot-starter 的奥秘
  • vue2使用render,js中写html
  • Spring整合Redis基本操作步骤
  • WPF 使用LibVLCSharp.WPF实现视频播放、停止、暂停功能
  • Vulnhub靶场Nginx解析漏洞复现
  • 防火墙技术与网络安全
  • 【Express】用express搭建本地服务器(轻松上手)
  • CSS系列(20)-- 自定义属性详解
  • 动态头部:利用注意力机制统一目标检测头部
  • 前端笔试面试题目——数据结构和算法篇(一)
  • 云手机能用来干什么?云手机在跨境电商领域的用途
  • SSM 架构上的 Vue 电脑测评系统:彰显科技评测魅力
  • XMLHttpRequest接受chunked编码传输的HTTP Response时有问题
  • 力扣第110题:平衡二叉树
  • MVVM、MVC、MVP 的区别
  • 前端篇-Content-Type 详解
  • 5G -- 空口关键技术
  • windows C#-实例构造函数
  • Linux基础(1)
  • JS里面Map的使用以及与Object的对比
  • 设计模式-读书笔记
  • 大数据——数据预处理
  • 【Spring】获取Bean对象需要哪些注解
  • 网络安全 | 防火墙的工作原理及配置指南
  • UE5材质系统之PBR材质
  • 天天 AI-241217:今日热点-谷歌版Sora升级4K高清!一句话控制镜头运动,跑分叫板可灵海螺