【贪心算法】之 分糖果(中等题)

2023-12-20 12:21:17
- n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
- 你需要按照以下要求,给这些孩子分发糖果:
		每个孩子至少分配到 1 个糖果。
		相邻两个孩子评分更高的孩子会获得更多的糖果。
		请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
这道题目一定是要确定一边之后,再确定另一边,先比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼
解题思路:
  1. 初始化两个数组left、right;每个小孩至少都有一个candy,所以初始化数组值为1;
  2. 分两个规则,从左边遍历数组,num[ i+1] >num[i],则num[i+1]的糖果比num[i]多一个,记录在left中;
  3. 同理,右至左遍历学生成绩并记录在 right 中,可以保证所有学生糖数量 满足右规则
  4. 最后我们贪心,取以上 2 轮遍历 leftright 对应学生糖果数的 最大值 ,这样则 同时满足左规则和右规则 ,即得到每个同学的最少糖果数量。
import java.util.Arrays;
//分糖果
public class leetcode_135 {
    public static void main(String[] args) {
        int[] ratings = {1, 3, 2, 2, 1};
        System.out.println(candy(ratings));
    }
    public static int candy(int[] ratings) {
        int index = 0;
        //初始化两个数组
        int[] left=new int[ratings.length];
        int[] right=new int[ratings.length];
        //初始值都为1;
        Arrays.fill(left,1);
        Arrays.fill(right,1);
        //左规则
        for (int i = 0; i < ratings.length-1; i++) {
            if (ratings[i+1]>ratings[i]){
                left[i+1]=left[i]+1;
            }
        }
        //右规则
        for (int i = ratings.length-1; i>0; i--) {
            if (ratings[i-1]>ratings[i]){
                right[i-1]=right[i]+1;
            }
        }
        //找最大 求和即可
        int sum=0;
        for (int i = 0; i <ratings.length ; i++) {
            sum+=Math.max(left[i],right[i]);
        }
        return sum;
    }
}

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