分发糖果

Leetcode Link: 135. 分发糖果 - 力扣（LeetCode）

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

解法一

思路：参考

假设学生 A 和学生 B 相邻，A 在 B 的左边

规则定义：

• 左规则： 当 ${\text{ratings}}_B$ > ${\text{ratings}}_A$ 时，B 得到的糖比 A 多
• 右规则： 当 ${\text{ratings}}_A$ > ${\text{ratings}}_B$ 时，A 得到的糖比 B 多

相邻的学生中，评分高的学生得到的糖果多 等价于 所有学生既满足左规则又满足右规则

算法流程：

1. 先从左至右遍历学生成绩 ratings，按照以下规则给糖，并记录在 left 中
   1. 先给所有学生 1 颗糖
   2. 若 ratings[i]>ratings[i-1]，则第 i 名学生糖比第 i - 1 名学生多 1 个
   3. 反之，第 i 名学生的糖的数量不变
2. 同理，在此规则下从右至左遍历学生成绩并记录在 right 中，可以保证所有学生糖数量 满足右规则 。
3. 最终，取以上 2 轮遍历 left 和 right 对应学生糖果数的 最大值 ，这样则 同时满足左规则和右规则 ，即得到每个同学的最少糖果数量

题解： 自己写代码

class Solution:
    def candy(self, ratings: List[int]) -> int:
        res1 = [1]*len(ratings)
        res2 = [1]*len(ratings)
        # 从前往后，判断 右>左
        for i in range(1,len(ratings)): 
            if ratings[i] > ratings[i-1]:
                res1 [i] = res1 [i-1] + 1
        # 从后往前，判断 左>右
        for i in range(len(ratings)-2, -1, -1): # 注意索引边界
            if ratings[i+1] < ratings[i]:
                res2[i] = res2[i+1] + 1
        res = 0
        for val1, val2 in zip(res1, res2):
            res += max(val1, val2)
        return res

网友的优化代码，只使用一个结果变量

class Solution:
    def candy(self, ratings: List[int]) -> int:
        res = [1] * len(ratings)
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                res[i] = res[i - 1] + 1
        for j in range(len(ratings) - 2, -1, -1):
            if ratings[j] > ratings[j + 1]:
                res[j] = max(res[j], res[j + 1] + 1)
        return sum(res)

启发和联系

对于题目中的要求能够拆成满足多种条件，是不是可以一个一个的条件来满足，然后最后将所有条件的答案通过某种方式合并成最终答案？

相关题目：根据身高重建队列