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

小咪咪 2022-10-10 12:47 230阅读 0赞

## 题目 ##

[https://leetcode.com/problems/candy/][https_leetcode.com_problems_candy]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

#### 思路 ####

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

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

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

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

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

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

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

得到下面这个结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
观察上面这个结果，它表示了前后之间的单调关系，现在我们需要根据这个单调关系，给每一个位置分糖果。

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

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

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

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

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

后面的位置以此类推，就省略了。得到的结果应该是这样的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]  
为了便于描述，我们蓝框内的序列分别称作 **序列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;
        }
    }

补一张草稿：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]

第一次做 hard 题，写了 2.5h。。时间主要花在调整细节、以及初始思路没有照顾到的地方导致的 bug 上了。再接再厉吧~  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]

[https_leetcode.com_problems_candy]: https://leetcode.com/problems/candy/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/78c42a8b027842599695347f0f67c30c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/fae346103b4d4aa3bc3f333c9a7c7854.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/fb95d5972317450bb5e9b8b59d2e65cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20221005/66052b8e6c2941a1aa0c95ca1b67b48c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]: /images/20221005/3aee0dd84da148cdb69a66fcb84fd340.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]: /images/20221005/2202da44124646d38e682b50406e2200.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]: /images/20221005/74505650167e4c6fa43e84435970b40c.png