想要精通算法和SQL的成长之路 - 分发糖果

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 分发糖果

原题链接

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：

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

那么这样下来，老师至少需要准备多少颗糖果呢？示例 1:

• 输入: [1,0,2]
• 输出: 5
• 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

1.1 贪心法分析

思路：我们用candy[i]代表这个孩子拥有的糖果数。初始化时，每个小朋友有一个糖果。

int[] candy = new int[ratings.length];
Arrays.fill(candy, 1);
1
2

先从左往右遍历：

• 只考虑右侧评分大于左侧评分的孩子，给他多分一个糖果。（局部最优）
• 此时能保证，相邻的两个孩子，右侧孩子的糖果数一定 >= 左侧孩子的糖果数。
• 如果右侧孩子评分更高，那么他的糖果数应该是左侧孩子的糖果数candy[i] + 1。

for (int i = 0; i < ratings.length - 1; i++) {
    // 右侧孩子评分比左侧孩子高
    if (ratings[i + 1] > ratings[i]) {
        candy[i + 1] = candy[i] + 1;
    }
}
1
2
3
4
5
6

---

再从右往左遍历：

• 只考虑左侧评分大于右侧评分的孩子。那么此时需要保证左侧孩子的糖果数一定要保证比右侧大。（局部最优）

那么此时有两种可能：

• 第一种：candy[i]（左侧） < candy[i+1]（右侧），那么左侧孩子的的糖果数应该是candy[i+1]+1。
• 第二种：candy[i]（左侧） > candy[i+1]（右侧），那么左侧孩子的的糖果数应该是candy[i]。因为已经满足条件了，不用再给他了。

总结就是candy[i] = Math.max(candy[i],candy[i+1]+1)

for (int i = ratings.length - 2; i >= 0; i--) {
    // 左侧孩子评分比右侧孩子高
    if (ratings[i] > ratings[i + 1]) {
        candy[i] = Math.max(candy[i], candy[i + 1] + 1);
    }
}
1
2
3
4
5
6

同时满足两个局部最优，那么最终结果就是全局最优了。

1.2 最终完整代码

public int candy(int[] ratings) {
    int[] candy = new int[ratings.length];
    // 初始化糖果，让每个孩子都至少有1个。
    Arrays.fill(candy, 1);
    // 第一次从左往右遍历
    for (int i = 0; i < ratings.length - 1; i++) {
        // 右侧孩子评分比左侧孩子高
        if (ratings[i + 1] > ratings[i]) {
            candy[i + 1] = candy[i] + 1;
        }
    }
    // 第二次从右往左遍历
    for (int i = ratings.length - 2; i >= 0; i--) {
        // 左侧孩子评分比右侧孩子高
        if (ratings[i] > ratings[i + 1]) {
            candy[i] = Math.max(candy[i], candy[i + 1] + 1);
        }
    }
    return Arrays.stream(candy).sum();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20