题目

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

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

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

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

示例 1：

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

示例 2：

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

提示：

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

题解

我的思路解不出来，答案有问题，那么就说一下一个很巧妙的正确解法：

根据题目的要求，最后的糖果数组应该满足：

若学生A与学生B左右相邻，A在B左边：

  • 左规则：当ratings[B] > ratings[A]时，B的糖比A多；

  • 右规则：当ratings[A] > ratings[B]时，A的糖比B多；

那么，我们先将每个人的糖果初始化为1，然后先对letf数组应用左规则，当左边的比右边的分数高，就在右边的基础上多发一个；再对right数组应用右规则，当右边的比左边的分数高，就在左边的基础上多发一个。然后选取每个位置的left与right最大值（同时满足左右规则），便是答案。

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
class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] left = new int[len];
        int[] right = new int[len];
        // 初始化数组
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        // 左规则，从第二个开始（第一个默认为1）
        for(int i = 1; i < len; i++) {
            if(ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        // 因为从倒数第二个开始，count初始值为left[len - 1]，right[len - 1]为1，left[len - 1]必然大于等于right[len - 1]
        int count = left[len - 1];
        // 右规则，从倒数第二个开始（反方向的左规则）
        for(int i = len - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
            // 选择最大的数进行求和
            count += Math.max(left[i], right[i]);
        }
        return count;
    }
}