135. 分发糖果

给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子中，评分更高的那个会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

1 <= n == ratings.length <= 5 * 10的4次方
0 <= ratings[i] <= 5 * 10的4次方

题解：

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ans = n; // 第一步：每人先发1颗基础糖，总和先记为n

        // 外层循环：一次处理一整座山，i 跳到山的末尾
        for (int i = 0; i < n; i++) {
            // 1. 确定当前山的起点 start
            // 处理「谷底共享」：如果当前位置比左边高，说明左边i-1是谷底，属于当前山的起点
            int start = i > 0 && ratings[i - 1] < ratings[i] ? i - 1 : i;

            // 2. 找严格递增段，走到峰顶
            while (i + 1 < n && ratings[i] < ratings[i + 1]) {
                i++;
            }
            int top = i; // 循环结束，i 就是峰顶的下标

            // 3. 找严格递减段，走到山的末尾
            while (i + 1 < n && ratings[i] > ratings[i + 1]) {
                i++;
            }

            // 4. 计算递增、递减段的长度
            long inc = top - start; // 递增段的间隔数
            long dec = i - top;     // 递减段的间隔数

            // 5. 把这座山的额外糖果加到总答案里,根据等差数列求和公式
            ans += (inc * (inc - 1) + dec * (dec - 1)) / 2 + Math.max(inc, dec);
        }
        return ans;
    }
}

分析

题目要求，每个孩子至少分 1 颗糖果。我们先给每个孩子 1 颗糖果，下面就不用考虑这个要求了，可以给孩子最少 0 颗糖果。

题目要求，相邻两个孩子评分更大的孩子会获得更多的糖果。如何理解这句话呢？

比如 ratings=[1,2,3,4,5,4,3,2]，由严格递增段 [1,2,3,4]、峰顶 5 和严格递减段 [4,3,2] 组成。

对于严格递增段，最左边的孩子旁边没有评分比他小的孩子，所以给他 0 颗糖果就行（注意我们在一开始给了每个孩子一颗糖果），下一个孩子的糖果必须比上一个孩子的多，贪心地，多 1 就行。所以分给严格递增段的糖果数为 0,1,2,3。

对于严格递减段，最右边的孩子旁边没有评分比他小的孩子，所以给他 0 颗糖果就行（注意我们在一开始给了每个孩子一颗糖果），往左看，左边孩子的糖果必须比右边孩子多，贪心地，多 1 就行。所以分给严格递减段的糖果数为 2,1,0。

最后确定峰顶的糖果数，必须比严格递增段的最大值多，即 ≥4；也必须比严格递减段的最大值多，即 ≥3，取 max(4,3)=4 作为峰顶的糖果数。

把严格递增段 + 峰顶 + 严格递减段叫做一座山。

如果数组中只有一座山，计算糖果总数是简单的。但如果有多座山呢？如何找到每座山？

分组循环

适用场景：按照题目要求，数组会被分割成若干组，每一组的判断/处理逻辑是相同的。

核心思想：

外层循环负责遍历组之前的准备工作（记录开始位置），和遍历组之后的统计工作（更新答案）。

内层循环负责遍历组，找出这一组最远在哪结束。

这个写法的好处是，各个逻辑块分工明确，也不需要特判最后一组（易错点）。以我的经验，这个写法是所有写法中最不容易出 bug 的，推荐大家记住。

详细计算过程

以 ratings=[1,2,3,4,2,1,4,5,2] 为例说明：

第一组，先上坡再下坡，即 [1,2,3,4,2,1]。

记录起始下标 start=i=0。

写一个循环找严格递增段，如果 ratings[i]<ratings[i+1] 就继续循环。循环结束时 i 就是峰顶下标，记作 top。这里 top=3。

写一个循环找严格递减段，如果 ratings[i]>ratings[i+1] 就继续循环。循环结束时 i 就是严格递减段最后一个数的下标。这里 i=5。

设 inc=top−start。从 start 到 top−1，分到的糖果数依次为 0,1,2,…,inc−1（注意我们在一开始给了每个孩子一颗糖果），根据等差数列求和公式，得糖果总数为

2inc(inc−1)。这里 inc=3，糖果总数为 0+1+2=3。

设 dec=i−top。从 top+1 到 i 到，分到的糖果数依次为 dec−1,dec−2,…,0，根据等差数列求和公式，得糖果总数为

2dec(dec−1) 。这里 dec=2，糖果总数为 0+1=1。

峰顶的糖果数为 max(inc,dec)=3。

把 i 加一，找下一组。

第二组，先上坡再下坡，即 [1,4,5,2]。做法同上。

注意这里的 1 也是前一组的最后一个数（谷底会被两组共享）。在记录 start 时，如果 i>0 且 ratings[i−1]<ratings[i]，说明 i−1 是谷底，记录 start=i−1，否则记录 start=i。

⚠注意：我们在一开始给了每个孩子一颗糖果，在后面分组循环的计算过程中，不考虑一开始分的这颗糖果。第一组的最后一个数虽然也在第二组的第一个数中，但由于这个孩子在分组循环中分到的糖果数是 0，所以不会重复统计。

对于 ratings=[1,2,2,3] 这种包含相邻相同元素的情况，按照上文的规则，分成两组 [1,2] 和 [2,3]。糖果数为 0,1,0,1。

特别地，如果一组的第一个数是峰顶，则 inc=0；如果一组的最后一个数是峰顶，则 dec=0。

示例 1 ratings=[1,0,2]，分成两组 [1,0] 和 [0,2]。答案为 3（先给每个孩子一颗糖果）加上 1+0 加上 0+1 等于 5。

示例 2 ratings=[1,2,2]，分成两组 [1,2] 和 [2]。答案为 3（先给每个孩子一颗糖果）加上 0+1 加上 0 等于 4。

总结

先给每个孩子一颗糖果，即初始化答案为数组长度 n。

然后用分组循环计算每一组（严格递增段 + 峰顶 + 严格递减段）的 inc 和 dec，把答案增加

复杂度分析

时间复杂度：O(n)，其中 n 是 ratings 的长度。时间复杂度乍一看是 O(n 2 )，但注意变量 i 只会增加，不会重置也不会减少。所以二重循环总共循环 O(n) 次，所以时间复杂度是 O(n)。

空间复杂度：O(1)。

作者：灵茶山艾府

链接：https://leetcode.cn/problems/candy/solutions/3691236/fen-zu-xun-huan-ba-kun-nan-ti-bian-cheng-fo15/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。