LeetCode 135. 分发糖果

Categories:

题目描述
思路分析
1. 解法一：两次贪心扫描（推荐）
2. 解法二：单次遍历（常数空间）
相似题目

题目描述

✅ 135. 分发糖果

思路分析

解法一：两次贪心扫描（推荐）

核心思路：

每个孩子至少分 1 颗糖果，先初始化 candies[i] = 1。

第一次从左到右扫描：若 ratings[i] > ratings[i-1]，则 candies[i] = candies[i-1] + 1，保证右邻比左邻评分高时糖果也多。

第二次从右到左扫描：若 ratings[i] > ratings[i+1]，则 candies[i] = max(candies[i], candies[i+1] + 1)，保证左邻比右邻评分高时糖果也多。

两次扫描后，每个孩子都同时满足”比左邻多”和”比右邻多”的约束，累加即为最少糖果总数。

复杂度分析：

时间复杂度：O(n)，其中 n 为孩子数，两次线性扫描

空间复杂度：O(n)，需要额外的 candies 数组存储每个孩子的糖果数

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        // 初始化每人至少 1 颗
        Arrays.fill(candies, 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] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // 累加所有糖果
        int total = 0;
        for (int c : candies) {
            total += c;
        }
        return total;
    }
}

func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)

    // 初始化每人至少 1 颗
    for i := range candies {
        candies[i] = 1
    }

    // 从左到右：保证评分更高的右邻获得更多糖果
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }

    // 从右到左：保证评分更高的左邻获得更多糖果
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            if candies[i+1]+1 > candies[i] {
                candies[i] = candies[i+1] + 1
            }
        }
    }

    // 累加所有糖果
    total := 0
    for _, c := range candies {
        total += c
    }
    return total
}

解法二：单次遍历（常数空间）

核心思路：

观察评分序列中的”上升段”和”下降段”：

上升段长度 up，下降段长度 down，当前连续平坡 peak。

遍历时维护 up、down、peak 三个计数器，规律如下：

评分递增：up++，down = 0，糖果增量为 up + 1。

评分递减：down++，糖果增量为 down；若 down >= peak，还需额外补 1 给波峰（波峰要比下降段第一个更大）。

评分相等：up = down = 0，peak = 0，糖果增量为 1。

核心思路是将整个序列分解为若干”上坡 + 下坡”片段，分别计算每段的最小糖果数。

复杂度分析：

时间复杂度：O(n)，其中 n 为孩子数，单次线性扫描

空间复杂度：O(1)，只使用常数个变量

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n == 1) {
            return 1;
        }
        // total: 糖果总数；up: 连续上升长度；down: 连续下降长度；peak: 上坡最高点分配数
        int total = 1, up = 0, down = 0, peak = 0;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                // 进入上升段，重置下降计数
                up++;
                down = 0;
                peak = up;
                total += up + 1;
            } else if (ratings[i] < ratings[i - 1]) {
                // 进入下降段，重置上升计数
                down++;
                up = 0;
                // 若下降段长度超过波峰，需给波峰额外加 1
                total += down + (down >= peak ? 1 : 0);
            } else {
                // 平坡：重置所有计数
                up = 0;
                down = 0;
                peak = 0;
                total += 1;
            }
        }
        return total;
    }
}

func candy(ratings []int) int {
    n := len(ratings)
    if n == 1 {
        return 1
    }

    // total: 糖果总数；up: 连续上升长度；down: 连续下降长度；peak: 上坡最高点分配数
    total, up, down, peak := 1, 0, 0, 0
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            // 进入上升段，重置下降计数
            up++
            down = 0
            peak = up
            total += up + 1
        } else if ratings[i] < ratings[i-1] {
            // 进入下降段，重置上升计数
            down++
            up = 0
            // 若下降段长度超过波峰，需给波峰额外加 1
            extra := 0
            if down >= peak {
                extra = 1
            }
            total += down + extra
        } else {
            // 平坡：重置所有计数
            up = 0
            down = 0
            peak = 0
            total++
        }
    }
    return total
}

相似题目

题目	难度	考察点
455. 分发饼干	简单	贪心、排序
406. 根据身高重建队列	中等	贪心、排序
1005. K 次取反后最大化的数组和	简单	贪心
860. 柠檬水找零	简单	贪心、模拟
56. 合并区间	中等	贪心、排序
763. 划分字母区间	中等	贪心、双指针
45. 跳跃游戏 II	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/28450664