Leetcode 135 分发糖果

2023-12-21 16:44:16

题意理解

? ? ? ? 给出n个小孩的得分,给他们奖励糖果

? ? ? ? 奖励条件

? ? ? ? ? ? ? ? (1)每个孩子至少分配到?1?个糖果。

????????????????(2)相邻两个孩子评分更高的孩子会获得更多的糖果。

????????

????????对于任意一个小孩,她要比左右两边的小孩分数都高,则她得到的糖要比两个小孩都多,至少多1。

? ? ? ? 对于任意一个小改,她要比左右两个小孩分数都低,则她得到的糖要比两个小孩都少,至少少1,且她最少得到一颗糖。

? ? ? ? 目标是:如何分发最少的糖,且满足分发条件

解题思路

? ? ? ? 采用贪心的方法来解题,则全局最优是满足分发条件的最少的糖。

? ? ? ? 每个孩子至少获得一颗糖,分少的孩子糖数尽可能的少,则再为分高的孩子发更多的糖,且需保证用糖最少。

? ? ? ? 每个孩子即需要和左边的孩子比,也需要和右边的孩子比。

? ? ? ? 为简化问题

????????????????我们和左边的孩子比,分比左边的大,则糖=左边孩子糖数+1

? ? ? ? ????????其次我们再和右边的孩子比,若比右边的孩子大,则糖 = Max (糖,右边孩子糖数+1)。

? ? ? ? ????????最终我们保证每个孩子得到的糖数满足分发条件且最少。
? ? ? ? ? ? ? ?

1.贪心解题

public int candy(int[] ratings) {
        int candiesSum=0;
        int[] candies=new int[ratings.length];
        //每个孩子初始化糖1
        Arrays.fill(candies,1);
        //和左边的孩子比
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                candies[i]=candies[i-1]+1;//至少左边的孩子多一个糖
            }
        }
        //和右边的孩子比
        for(int i= ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candies[i]=Math.max(candies[i+1]+1,candies[i]);//保证即满足左孩子,又比右孩子多
            }
        }
        //统计糖
        for(int i=0;i<candies.length;i++) candiesSum+=candies[i];
        return candiesSum;
    }

2.分析

时间复杂度:O(n)

空间复杂度:O(n)

n为输入数组长度。

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135131602
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。