LeetCode 135. 分发糖果

◎

本节目标

将左右相邻的评分约束拆成两次单向扫描，再取每人所需糖果的较大值。

这是局部约束与构造中双向局部约束的母题。

题意与约束

每个孩子至少获得一颗糖；评分高于相邻孩子时，糖果数也必须更多。求满足全部相邻约束的最少糖果总数。

直接思路与瓶颈

不断修改违反约束的位置可以得到答案，却难以控制结束轮数。左右关系相互影响，单次从左扫描也无法处理下降段。

贪心模型与算法推导

先令每人一颗糖。从左到右处理“比左邻居评分高”的约束；再从右到左处理“比右邻居评分高”的约束，并取已有值与右侧需求的最大值。

正确性依据

第一次扫描给出满足左侧约束的最小配置，第二次扫描给出满足右侧约束的最小配置。每个人同时满足两侧所需糖果的最小值正是两份需求的最大值；逐位取最大不会破坏已满足的另一侧约束，且没有多发糖果。

样例执行过程

[1,0,2] 初始为 [1,1,1]。左扫后仍为 [1,1,2]；右扫处理第 0 位，令其至少为右边 1+1，得到 [2,1,2]，总数 5。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int candy(vector<int> ratings) {
        const int n = static_cast<int>(ratings.size());
        vector<int> candies(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) candies[i] = max(candies[i], candies[i + 1] + 1);
        }
        int answer = 0;
        for (int amount : candies) answer += amount;
        return answer;
    }
};

Python

Python 3

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

复杂度分析

两次线性扫描，时间 O(n)；糖果数组占用 O(n) 额外空间。

边界与易错点

• 评分相等不产生严格更多的约束。
• 右扫更新必须取最大值，不能直接覆盖左扫结果。
• 全部相等时每人一颗糖。

模式迁移

当线性序列同时存在左侧和右侧的单调约束时，常可拆为两次方向相反的最小需求传播。