135.分发糖果(Hard)

题目描述

一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一 个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所 有孩子至少要有一个糖果。求解最少需要多少个糖果。

样例

Input: [1,0,2]
Output: 5
# 解释 发送糖果数为[2,1,2]

Input: [1,2,2]
Output: 4
# 解释 发送糖果数为[1,2,1]。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

题解

贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。

第一步：从左向右遍历，比较左边的孩子的分数，如果大的话就比左孩子加一。

第二步：从右向左遍历，调整当前糖果数是否符合条件。

经过两遍的调整，符合题意

图解：https://leetcode-cn.com/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/

代码示例

Python 示例

使用两个数组，left 和 right 记录

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

Go 示例

使用两个数组，left 和 right 记录

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func candy(ratings []int) int {
    n := len(ratings)
    left := make([]int, n)
    right := make([]int, n)
    for i := 0; i < n; i++ { // 每个小朋友都至少发一颗糖
        left[i] = 1
        right[i] = 1
    }

    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i - 1] { 
            left[i] = left[i - 1] + 1
        }
    }
    count := left[n - 1]
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i + 1] {
            right[i] = right[i + 1] + 1
        }
        count += max(left[i], right[i])
    }
    return count

只使用一个数组

func candy(ratings []int) int {
    n := len(ratings)
    candy := make([]int, n)
    for i:=0; i < n; i++ {
        candy[i] = 1
    }

    for i:= 1; i < n; i++ {
        if ratings[i] > ratings[i - 1] {
            candy[i] = candy[i - 1] + 1
        }
    }

    for i:= n - 2; i >=0; i-- {
        if ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1] {
            candy[i] = candy[i + 1] + 1
        }
    }

    ans := 0
    for i:= 0; i < n ; i++ {
        ans += candy[i]
    }
    return ans 
}