力扣:135. 分发糖果(贪心)

发布时间:2023年12月28日

题目:

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

思路:

这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼

先确定右边评分大于左边的情况(也就是从前向后遍历)

此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

代码如下:

        # 从左到右遍历ratings数组,如果当前孩子的评分比前一个孩子高,则糖果数量加1
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candy[i] = candy[i - 1] + 1

再确定左孩子大于右孩子的情况(从后向前遍历)

        # 从右到左遍历ratings数组,如果当前孩子的评分比后一个孩子高,则取当前糖果数量和后一个孩子糖果数量加1的最大值
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candy[i] = max(candy[i + 1] + 1, candy[i])

这在leetcode上是一道困难的题目,其难点就在于贪心的策略,如果在考虑局部的时候想两边兼顾,就会顾此失彼。

那么本题采用了两次贪心的策略:

  • 一次是从左到右遍历,只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历,只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优,即:相邻的孩子中,评分高的孩子获得更多的糖果。

?

整体代码:

class Solution:
    def candy(self, ratings: List[int]) -> int:
        # 初始化每个孩子的糖果数量为1
        candy = [1] * len(ratings)
        result = 0
        # 从左到右遍历ratings数组,如果当前孩子的评分比前一个孩子高,则糖果数量加1
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candy[i] = candy[i - 1] + 1
        # 从右到左遍历ratings数组,如果当前孩子的评分比后一个孩子高,则取当前糖果数量和后一个孩子糖果数量加1的最大值
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candy[i] = max(candy[i + 1] + 1, candy[i])
        # 计算总糖果数量
        for i in range(len(candy)):
            result += candy[i]
        return result

复杂度分析:

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