LeetCode之分发糖果(135)--Java

1.问题描述

          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 * 10

        难度等级

                困难

        题目链接

                分发糖果

2.解题思路

        这道题是一道十分典型的贪心题目，让我们来一起看看如何AC它吧。

        首先，我们要初始化一个存储存储糖果的糖果数组，并且按照题目要求，每个小孩至少一颗糖果，将数组的值初始化为1。

        //记录糖果数组
        int[] candies = new int[ratings.length];
        //初始化糖果数组
        for(int i = 0;i < ratings.length;i++){
            candies[i] = 1;
        }

         题目要求小孩如果评分比相邻的孩子高，那么分配的糖果也要比相邻的孩子多，这就涉及到了左右的比较。我们可以把左右的比较拆开来，先和左边的比较，然后再返过来和右边的比较。

        用一个for循环从左向右遍历，如果当前孩子的评分比它左边的孩子高，那么当前孩子的糖果就要比左边那个孩子多一颗(因为要求最少的糖果，所以我们只给多一颗，贪心资本家的体现)，如果评分和左边的孩子相等或者比左边的孩子低，不做处理，还是一颗。我们这一轮循环主要解决左边的孩子比当前孩子评分高的情况。遍历完成之后，就确保了，每一个孩子，如果左边的孩子比自己评分低，糖果一定比自己少。

        //从左到右遍历，确保每个孩子如果评分比左边的孩子高，
        //糖果至少比左边的孩子多1
        for(int i = 1;i< ratings.length;i++){
            if(ratings[i] > ratings[i-1]){
                candies[i] = candies[i-1]+1;
            }
        }

        接着，再用一个for循环从右向左遍历，如果当前孩子的评分比它右边的孩子高。那么当前这个孩子的糖果至少要比右边那个孩子多一颗，但是我们还要保持如果比左边的孩子评分高，当前孩子的糖果也要比左边多，所以我们要在当前孩子已经有的糖果和比右边那个孩子的糖果多一颗这两个数量中取最大值，这样才能同时满足孩子如果评分比相邻孩子高，那么分配的糖果也要比相邻孩子多。遍历完成之后，就确保了，每一个孩子，如果右边的孩子评分比自己低，糖果一定比自己少。

        //从右向左遍历，确保每个孩子如果评分比右边的孩子高，
        //糖果至少比右边的孩子多1
        for(int i = ratings.length-2;i>=0;i--){
            if(ratings[i] > ratings[i+1]){
                candies[i] = Math.max(candies[i],candies[i+1]+1);
            }
        }

        两个循环遍历下来，我们已经解决了糖果的数量问题，最后统计一下每个孩子的糖果，累加起来就是所需糖果的最小总数了。

        //统计糖果数目
        int result = 0;
        for(int i = 0;i < candies.length;i++){
            result += candies[i];
        }

3.代码展示

class Solution {
    public int candy(int[] ratings) {
        //记录糖果数组
        int[] candies = new int[ratings.length];
        //初始化糖果数组
        for(int i = 0;i < ratings.length;i++){
            candies[i] = 1;
        }
        //从左到右遍历，确保每个孩子如果评分比左边的孩子高，
        //糖果至少比左边的孩子多1
        for(int i = 1;i< ratings.length;i++){
            if(ratings[i] > ratings[i-1]){
                candies[i] = candies[i-1]+1;
            }
        }
        //从右向左遍历，确保每个孩子如果评分比右边的孩子高，
        //糖果至少比右边的孩子多1
        for(int i = ratings.length-2;i>=0;i--){
            if(ratings[i] > ratings[i+1]){
                candies[i] = Math.max(candies[i],candies[i+1]+1);
            }
        }
        //统计糖果数目
        int result = 0;
        for(int i = 0;i < candies.length;i++){
            result += candies[i];
        }
        return result;
    }
}

4.总结

        这道题使用贪心算法来解决，其实并不难，需要跟左右两边比较的情况下，我们可以先比较一边，然后再保证前面的比较结果的基础上，比较另外一边，最后统计糖果数量即可。好了，这道题就简单啰嗦到这，祝大家刷题愉快~

原文地址：https://blog.csdn.net/2301_79318558/article/details/143504996

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！