LeetCode 135 分发糖果 • Sun Blog

LeetCode 题目链接 ↗

题目描述#

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

题解#

我们首先来看一个典型的 「山峰」型评分序列：

ratings = [1, 2, 3, 4, 5, 3, 2, 1]

java

由于每个孩子至少应获得一个糖果，我们首先为每个孩子分配一个糖果，即糖果的初始总数为 n = ratings.length。

对于该「山峰」序列，我们可以分为两个部分进行分析：

递增部分：

第 0 个孩子可额外分配 0 个糖果（不计初始分配的 1 个糖果）
第 1 个孩子可额外分配 1 个糖果
第 2 个孩子可额外分配 2 个糖果
第 3 个孩子可额外分配 3 个糖果
第 4 个孩子可额外分配 4 个糖果

递减部分：

第 7 个孩子可额外分配 0 个糖果
第 6 个孩子可额外分配 1 个糖果
第 5 个孩子可额外分配 2 个糖果
第 4 个孩子可额外分配 3 个糖果

由于第 4 个孩子处于 「峰顶」 ，在递增和递减序列中均被计入，因此其糖果数取两部分的最大值，即 max(4, 3) = 4。

因此，总糖果数为：

n + (0 + 1 + 2 + 3) + (0 + 1 + 2) + max(4, 3)

java

我们可以将评分序列划分为多个“山峰”结构，并依据上述规则贪心地求解每一段的局部最优，从而获得整体的全局最优解

算法流程如下：

初始下标 start = 0，通过循环 ratings[i] < ratings[i+1] 找到递增序列，循环结束时的下标即为峰顶 top。
接着通过循环 ratings[i] > ratings[i+1] 找到递减序列，循环结束时的下标即为谷底。
设 up = top - start 为递增序列的长度（不考虑峰顶），则分到的糖果依次为 0, 1, 2, ..., up - 1, 等差数列求和结果为 up * (up - 1) / 2。
设 down = i - top 为递减序列的长度（不考虑峰顶），则分到的糖果依次为 down - 1, down - 2, ..., 0，等差数列求和结果为 down * (down - 1) / 2
峰顶元素的糖果数为 max(up, down)。
继续处理下一段「山峰」序列，令 start = i，两段序列共用谷底元素。
若存在“平峰”（如 [1, 2, 2, 3]），则划分为 [1, 2] 和 [2, 3] 两段，此时第一段的递减长度为 0，第二段的递增长度为 0，两者不共享谷底元素。因此，需通过如下判断更新 start：

start = i + 1 < n && ratings[i] < ratings[i + 1] ? i : i + 1;

java

完整代码如下：

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int res = n;
        int start = 0;

        for(int i = 0; i < n; i++) {
            // 找到峰顶
            while(i + 1 < n && ratings[i] < ratings[i+1])
                i++;
            int top = i;

            // 找到谷底
            while(i + 1 < n && ratings[i] > ratings[i+1])
                i++;
            
            int up = top - start;
            int down = i - top;

            res += (up * (up - 1) + down * (down - 1)) / 2 + Math.max(up, down);

            // 处理平峰情况
            start = i + 1 < n && ratings[i] < ratings[i + 1] ? i : i + 1;
        }

        return res;
    }
}

java