点击获取AI摘要

135. 分发糖果 H

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 * 10⁴
0 <= ratings[i] <= 2 * 10⁴

方法一：双向扫描（Two-Pass Scan）

问题分析

在这道题中，需要满足以下两个约束：

每个孩子至少分到 $1$ 个糖果。
如果相邻两个孩子中某个孩子的评分更高，则他必须得到比另一人更多的糖果。

因为约束只涉及「相邻」两人的评分关系，我们可以拆分成“只考虑左侧约束”和“只考虑右侧约束”两个子问题，再将结果合并，既能保证全局最优，也能以线性时间得到答案。

算法思路

令 $n$ $n$ 为孩子数量。构造两个长度为 $n$ $n$ 的数组：
- left2right[i]：表示在仅考虑“左邻”约束（即若 $ratings[i] > ratings[i-1]$ 则要多分一颗）的情况下，孩子 $i$ 需要的糖果最少数量。
- right2left[i]：表示在仅考虑“右邻”约束（即若 $ratings[i] > ratings[i+1]$ 则要多分一颗）的情况下，孩子 $i$ 需要的糖果最少数量。
初始化：
- left2right = [1] * n
- right2left = [1] * n

因为每个孩子至少要 1 颗。

从左向右扫描（ $i$ 从 $1$ 到 $n-1$ ）：

如果 $ratings[i] > ratings[i-1]$ ，则
$left2right[i] = left2right[i-1] + 1$
否则，保持
$left2right[i] = 1$

从右向左扫描（ $i$ 从 $n-2$ 到 $0$ ）：

如果 $ratings[i] > ratings[i+1]$ ，则
$right2left[i] = right2left[i+1] + 1$
否则，保持
$right2left[i] = 1$

合并两个结果：对于每个位置 $i$ ，

$\text{candies}[i] = \max\bigl(left2right[i],\; right2left[i]\bigr)$

并累加求和得到最终答案：

$\sum_{i=0}^{n-1} \text{candies}[i]$

时间复杂度

左向扫描需要 $O(n)$ ，右向扫描需要 $O(n)$ ，合并结果再 $O(n)$ ，总共为

$O(n) + O(n) + O(n) = O(n)$

代码分解

初始化

left2right = [1] * n
right2left = [1] * n

左向扫描

访问下标 $i$ 从 $1$ 到 $n-1$
若 $ratings[i] > ratings[i-1]$ ，则 left2right[i] = left2right[i-1] + 1

右向扫描

访问下标 $i$ 从 $n-2$ 到 $0$
若 $ratings[i] > ratings[i+1]$ ，则 right2left[i] = right2left[i+1] + 1

合并结果并累加

遍历 $i=0$ 到 $n-1$
累加 max(left2right[i], right2left[i]) 到 total_candies

代码实现

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n == 0:
            return 0

        # 用于记录只考虑左邻关系时的最少糖果
        left2right = [1] * n
        # 用于记录只考虑右邻关系时的最少糖果
        right2left = [1] * n

        # 从左到右扫描
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left2right[i] = left2right[i - 1] + 1

        # 从右到左扫描
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right2left[i] = right2left[i + 1] + 1

        # 合并两边的结果，累加总糖果数
        total_candies = 0
        for i in range(n):
            total_candies += max(left2right[i], right2left[i])

        return total_candies

方法二：单次遍历（One-Pass Constant Space）

问题分析

我们希望只使用一个循环和 $O(1)$ 额外空间（常数空间），就能同时满足“相邻递增”和“相邻递减”两种约束。在一次遍历中，需要动态跟踪：

当前“递增段”走到了第几步，以便决定给当前孩子多少颗糖（直到出现下降）。
当前“递减段”从“峰值”开始下降的步数，以便合理分配下降序列中的糖果数，同时若下降长度追平了上一次递增的高度，还要额外给“峰值”多一颗糖。

算法思路

初始化：
- res = 1：累计总糖果数，从第 $0$ 个孩子开始，先给 1 颗。
- prev_candies = 1：上一位（索引 $i-1$ ）分到的糖果数。初始时，第 $0$ 位分了 1 颗。
- inc = 1：最近一次递增段结束时（或初始）的“峰值”孩子所分得的糖果数。
- dec = 0：当前“严格递减段”已经走了几步（从最近的峰值开始）。如果不在下降，就保持 $0$ 。
从索引 $i=1$ $i = 1$ 开始遍历到 $n-1$ $n - 1$ ：
- 如果 $ratings[i] \ge ratings[i-1]$ $r a t in g s [i] \geq r a t in g s [i - 1]$ （非严格下降）：
  1. 将 dec 清零：dec = 0，表示任何旧的下降段结束。
  2. 若 $ratings[i] == ratings[i-1]$ ，因为评分持平，不必给更多糖果：prev_candies = 1；
    否则（严格递增）则 prev_candies += 1。
  3. 将 res += prev_candies。
  4. 更新 inc = prev_candies：记录此刻递增段最新“峰值”孩子所分的糖数。
- 否则（即 $ratings[i] < ratings[i-1]$ $r a t in g s [i] < r a t in g s [i - 1]$ ，进入严格递减段）：
  1. 增加下降长度：dec += 1。
  2. 关键：如果 dec == inc，说明当前下降段已经追平了上一次递增段的“峰值”高度，需要让“峰值”孩子再多分 1 颗，以满足峰值两侧都比它少。于是执行 dec += 1（使当前下降序列每个孩子在分糖时都按照新的下降高度计算）。
  3. 给当前孩子分 dec 颗糖：res += dec。
  4. 由于当前处于下降段，下一步如果要重新递增，则需从 1 开始，故 prev_candies = 1。
遍历结束后，res 即为最少总糖果数。

在“下降”过程中，我们并不立即修改之前“递增段”的分配，而是用 dec 去累计下降序列中每个孩子应该分的糖数。若下降段长度没追平 inc，说明“峰值”孩子分糖数仍然大于下降序列中任何一个孩子，无需调整。如果追平，则在当前步调整下降长度（dec += 1），间接推高峰值，满足峰值两侧都比它少的要求。

时间复杂度

只进行一次从 $1$ 到 $n-1$ 的循环，循环体中操作为常数，所以总时间复杂度为 $O(n)$

代码分解

初始化常数变量

res = 1                 # 总糖果数，给第 0 个孩子 1 颗
prev_candies = 1        # i-1 位置孩子分到的糖果数
inc = 1                 # 最近一个递增段结束时的峰值分糖数
dec = 0                 # 当前递减段的长度

遍历下标 i 从 1 到 n-1

判断是“持平/递增”还是“递减”

if ratings[i] >= ratings[i - 1]:
    # 结算任何旧的递减段：重置 dec
    dec = 0
    # 如果持平，则 prev_candies = 1；否则严格递增 prev_candies += 1
    if ratings[i] == ratings[i - 1]:
        prev_candies = 1
    else:
        prev_candies += 1
    # 累加总糖果数
    res += prev_candies
    # 更新当前递增段的峰值分糖数
    inc = prev_candies
else:
    # 进入严格递减段
    dec += 1
    # 如果下降长度追平了上一次递增的高度，需要给峰值再 +1
    if dec == inc:
        dec += 1
    # 本轮降序孩子分 dec 颗
    res += dec
    # 处于下降段，下一轮递增需从 1 开始
    prev_candies = 1

循环结束，返回 res

代码实现

from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n == 0:
            return 0

        # 结果累计
        res = 1
        # 上一个孩子实际分到的糖果数；初始化第 0 个孩子为 1
        prev_candies = 1
        # 记录上一个递增段最后一个孩子分到的糖果数
        inc = 1
        # 当前递减段长度
        dec = 0

        for i in range(1, n):
            if ratings[i] >= ratings[i - 1]:
                # 只要不是严格递减，就要把递减状态清空
                dec = 0
                # 如果评分相等，则不给增量，直接给 1；否则递增逻辑：prev_candies + 1
                if ratings[i] == ratings[i - 1]:
                    prev_candies = 1
                else:
                    prev_candies += 1
                # 将本次糖果数累加到结果，并更新“递增段最后一颗” = prev_candies
                res += prev_candies
                inc = prev_candies
            else:
                # 进入严格递减段
                dec += 1
                # 如果当前下降长度等于之前递增段的高度，就需要再给峰值多 +1
                if dec == inc:
                    dec += 1
                # 本次在下降段里，孩子要分 dec 颗
                res += dec
                # 下降段里 prev_candies 不参考上一位，以便下次递增能从 1、2、3 … 开始
                prev_candies = 1

        return res