leetcode 135. Candy | 135. 分发糖果（原创图文详解，Java）

题目

https://leetcode.com/problems/candy/

题解

思路

首先，根据题意，这是一个分糖果问题。本题需要满足两个条件：

1. 每个孩子至少有一个糖果
2. rating 值较大的孩子，得到的糖果也较多（rating 值相等时随意）

通过分析可以发现，rating 值 本质上在确定 前后孩子 分到的糖果的 大小关系，也就是确定了前后之间的 单调性。而具体分到多少糖果与 rating 值无关，是由单调性决定的。

举一个例子，假设我们有下面这个序列：

8 4 4 3 9 2 5 5 9 9 9 1 2 2

我们比较后一个数字与前一个数字的大小关系，记为 help[]。

• 若大于，则记为 ↑
• 若小于，则记为 ↓
• 若等于，则记为 ？

得到下面这个结果：

观察上面这个结果，它表示了前后之间的单调关系，现在我们需要根据这个单调关系，给每一个位置分糖果。

一个简单的思路是贪心法。我们希望所有糖果的总数最小，就要从左向右开始，让每个位置上的糖果数量都最小。而由于需要保证每个孩子至少有一个糖果，所以我们 无法直接确定第一个孩子应该得到多少糖果，因为他会受到后面糖果数量的影响。

如果连第一个孩子的糖果数量都不能确定，那还怎么继续啊？没关系，对于每一个位置 n，我们 暂且分给他最少的糖果，让他能暂时满足当前的位置（n-1 和 n 的关系）就可以了。你可能要问了，后面的孩子怎么办？后面再调整 就好了。

举一个具体的例子，如下图。

对于 第 0 个位置 来说，因为它是 ?，所以他无欲无求，不和前面的孩子攀比，容易满足。目前只要给他 1 个糖果 就够了。

对于 第 1 个位置 来说，因为它是 ↓，所以他要比前面的孩子糖果少。为了保证不浪费，我们对糖果的增减幅度都为1。所以，第 1 个位置的糖果数量要比第 0 个位置的糖果数量少 1 个，也就是给第 1 个位置的孩子 0 个糖果 。那么问题来了，说好每个孩子至少有 1 个糖果呢？这个问题先放着，待会儿再调整。

下面来到 第 2 个位置。因为它是 ?，又是一个无欲无求的容易满足的孩子。这时候我们发现，对于无欲无求的孩子，不管前面的位置有多少糖果，我们 只要给他 1 个糖果就够了。它不受前面的影响，相当于 新开一个序列。新序列的开始，意味着上一个序列的结束。所以，在开启新序列之前，我们需要对上一个结束的序列进行 清算！
清算的时候，要保证上一个序列中每个孩子至少有 1 个糖果，所以要找到上一个序列中 糖果数量最少的孩子对应的糖果数量，这个值可能为负数。此时需要给每个孩子增加相同数量的糖果，直到这个糖果最少的孩子有 1 个糖果为止。其中，给上一序列中的每个孩子同时加相同数量的糖果，是为了满足前后单调关系。

另外，还有一种情况可以 新开序列，就是当 help 数组出现 ↑↓ 这种组合的时候，这个 ↓ 暂时不受前面糖果数量的约束，只需要给 1 个糖果就够了（引入了一个小坑，后面讲）。

后面的位置以此类推，就省略了。得到的结果应该是这样的：

清算的过程，需要照顾到前一个序列的末尾

上述清算的过程其实会引入一个小坑，只不过上面的数组比较特殊，没有发现而已。我们看下面这个例子。

为了便于描述，我们蓝框内的序列分别称作 序列1，序列2，序列3。

前面的过程看起来很正常，直到 index=7 的时候，问题出现了。此时我们需要 清算序列3，为了满足最少糖果数量要求，需将 1, 0 改为 2, 1。这时候序列 2 不开心了。在此之前，序列 2 末尾糖果数量是 2，index=4 位置的糖果是要比 index=5 位置的糖果多的。可现在 index=4,5 两个位置的糖果数量相等了，index=4 的孩子当然不愿意。

怎么办呢？给 index=4 的孩子补充糖果呗，直到他的糖果比 index=5 的糖果多为止。你可能会担心，给 index=4 的孩子补充糖果的操作，是否会引起他的前一个的孩子的不满？可以证明的是，不会存在这种情况。因为 根据序列的划分，只有在 ↑↓ 或 ? 的是时候才会新开序列，而在这两种情况中，只有在出现 ↑↓ 这种关系的时候，补充糖果操作才可能影响到前面的孩子，因为 ? 情况下的孩子是无欲无求的，他既可以比前面多，也可以比前面少。因此，增加判断条件（对应代码中的 line 20），使得需要补充糖果的孩子在 help 数组中肯定是个 ↑，说明他的糖果数本来就比前面的孩子多，所以无论增加多少，也不为过了。

上面这段话可能说的有点绕，总结起来就是：在 index=7 的时候清算 序列3，在清算的过程影响到了前一个序列的末尾，所以要给 序列2 的末尾补充糖果。

至此，整个清算过程就结束了。最后需要注意的是，到 for 循环结束时，是无法触发最后一个序列的清算的，最后一个序列需要独立清算。

代码

class Solution {
    public int candy(int[] ratings) {
        int[] help = new int[ratings.length]; // 含义：1=↑ 2=↓ 3=?
        help[0] = 3;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) help[i] = 1;
            else if (ratings[i] < ratings[i - 1]) help[i] = 2;
            else help[i] = 3;
        }
        int min = 1; // 当前序列最小糖果数量
        int sum = 1; // 全部糖果数量
        int cur = 1; // 当前位置需要糖果数量
        int count = 1; // 当前序列长度
        int curFirst = 1; // 当前序列起始位置糖果数量
        int preLast = Integer.MAX_VALUE; // 前一序列末尾位置糖果数量
        for (int i = 1; i < help.length; i++) {
            if (help[i] == 2 && help[i - 1] == 1 || help[i] == 3) { // ↑↓ 或 ?
                // 清算前一序列
                curFirst = curFirst + (1 - min);
                if (help[i - count] == 2) sum += Math.max(curFirst - preLast + 1, 0);
                preLast = cur + (1 - min); // ↑↓
                sum += (1 - min) * count;
                // 新开一个序列
                min = cur = curFirst = 1;
                count = 0;
            } else if (help[i] == 2) { // ↓
                cur -= 1;
                min = Math.min(min, cur);
            } else { // ↑
                cur += 1;
                min = Math.min(min, cur);
            }
            sum += cur;
            count++;
        }
        // 独立清算最后一个序列
        min = Math.min(min, cur);
        curFirst = curFirst + (1 - min);
        if (help[help.length - count] == 2) sum += Math.max(curFirst - preLast + 1, 0);
        sum += (1 - min) * count;
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

补一张草稿：

第一次做 hard 题，写了 2.5h。。时间主要花在调整细节、以及初始思路没有照顾到的地方导致的 bug 上了。再接再厉吧~