Ricky.L的随笔
0%

LeetCode.135.分发糖果（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.135.分发糖果（困难）

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

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

每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

题解

难点在于评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

思路

化繁为简，这里可以拆解为两个规则：

  • 左规则：当 ratings[i − 1] < ratings[i] 时，第i 个学生的糖果数量比第i − 1个孩子的糖果数量多。
  • 右规则：当 ratings[i] > ratings[i + 1] 时，第i 个学生的糖果数量比第i + 1个孩子的糖果数量多。

如何求解？

  • 先从左到右遍历评分数组，按左规则分配糖果。
  • 再从右到左遍历评分数组，按右规则分配糖果。
  • 最后同时满足左右规则的糖果数量就是最终结果，也就是取两者较大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    fun candy(ratings: IntArray): Int {
        if (ratings.isEmpty()) return 0
        val left = IntArray(ratings.size) { 1 }
        for (i in 1 until ratings.size) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1
            }
        }
        val right = IntArray(ratings.size) { 1 }
        for (i in ratings.size - 1 downTo 1) {
            if (ratings[i - 1] > ratings[i]) {
                right[i - 1] = right[i] + 1
            }
        }
        var sum = 0
        for (i in ratings.indices) {
            sum += maxOf(left[i], right[i])
        }
        return sum
    }
}

复杂度

  • 时间复杂度：O(n)，n 是孩子的数量，要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
  • 空间复杂度：O(n)，要保存所有的左、右规则对应的糖果数量。

空间优化

之前的解法已经把思路打开了，可以从左到右遍历分析看看能不能不占用额外空间就可以求解。

孩子的分数的排列无非是递增、递减、相等三种情况。

从左向右看：

  • 如果孩子分数相等，就分配1个糖果。
  • 如果孩子处于分数递增的序列中，可以发现糖果数量从左到右看是会从1开始递增，这样糖果分配数量才最少。
  • 如果孩子处于分数递减的序列中，可以发现糖果数量从左到右看是会递减到1，这样糖果分配数量才最少。
    • 如果从分配到1个糖果的孩子从右到左看，糖果数量是会递增到递减序列的开始位置。
    • 所以统计递减序列应该分配多少糖果，只要统计递减序列有多长，看做跟递增情况分配形式一样就行了。

递减序列的起点在哪？
rating[i] < rating[i - 1] && rating[i - 1] > rating[i - 2]时，i就是递减序列的起点。

边界情况

由于递增序列最后一个元素也可以算是递减序列的一个元素，所以它是受右规则约束的。

比如递增序列有3个元素，递减序列有8个元素，那么递增序列的第3个元素在递增遍历时分配了3个糖果，但最后实际应当分配9个糖果。这多的6个糖果应该怎么算进去？

可以发现如果递增序列和递减序列一样长：

  • 递增序列最后一个孩子和递减序列第一个孩子分配的糖果数量是一样的。
  • 这两个孩子的分数可能不一样。

这样的话要给递增序列最后一个孩子或递减序列第一个孩子多分配1个糖果的，才能满足左规则和右规则。

  • 如果递减序列比递增序列长1，就只能给递增序列最后一个孩子多分配2个糖果。
  • 如果递减序列比递增序列长2，就只能给递增序列最后一个孩子多分配3个糖果。
  • 如果递减序列比递增序列长3，就只能给递增序列最后一个孩子多分配4个糖果。

所以：如果递减序列比递增序列长x，就只能给递增序列最后一个孩子多分配x + 1个糖果。

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
44
45
46
47
48
49
class Solution {
    fun candy(ratings: IntArray): Int {
        val n = ratings.size
        // 上一个孩子的糖果数，第一个孩子默认分配1个糖果
        var pre = 1
        // 糖果数量，第一个孩子默认分配1个糖果
        var candies = 1
        // 递增序列长度，已经有一个孩子分配了糖果
        var inc = 1
        // 递减序列长度
        var dec = 0
        for (i in 1 until n) {
            when {
                ratings[i] == ratings[i - 1] -> {
                    // 分数持平，分配最少的糖果
                    candies += 1
                    pre = 1
                    
                    // 递增序列的开始，算递增序列第1个元素
                    inc = 1
                    // 糖果数为1时，递减序列还没开始或者刚结束
                    dec = 0
                }
                ratings[i] > ratings[i - 1] -> {
                    // 分数递增，比前一个孩子多分配一个糖果
                    val cur = pre + 1
                    candies += cur
                    pre = cur

                    // 递增序列长度在增加
                    inc = cur
                    // 递减序列还没开始
                    dec = 0
                }
                ratings[i] < ratings[i - 1] -> {
                    // 递减序列长度累加
                    dec++
                    // 给递增序列最后一个孩子多分配 `递减序列长度 - 递增序列长度` 个糖果
                    if (inc == dec) dec++
                    // 把递减序列当做递增序列看，最终分配形式是一样的
                    candies += dec
                    // 糖果数量递减到1时，要记录下来
                    pre = 1
                }
            }
        }
        return candies
    }
}

复杂度

  • 时间复杂度：O(n)，遍历一次数组。
  • 空间复杂度：O(1)，仅适用常数个变量。