分发糖果

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，135. Candy

先看题目描述

rg4TDf.png

大意就是给定一个 rating 数组代表每个孩子的分数，让我们给孩子分发糖果，要求每个孩子至少有一个糖果，且相邻的孩子中，评分高的 孩子必须获得更多的糖果，让我们返回要给出去的最小总糖果数

算法和思路

这道题不会做，看题解才知道该怎么做

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理

  • 左规则：当 ratings[i] > ratings[i - 1] 时，i 号学生的糖果数量要比 i - 1 号学生的糖果数量多
  • 右规则：当 ratings[i] > ratings[i + 1] 时，i 号学生的糖果数量要比 i + 1 号学生的糖果数量多

我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终被分得的糖果数量即为这两个数量的最大值

具体地，以左规则为例，我们从左到右遍历该数组，假设当前遍历到位置 i，如果有 ratings[i] > ratings[i - 1]，那么 i 号学生的糖果数量要比 i - 1 号学生的糖果数量多，则令 left[i] = left[i - 1] + 1 即可；否则令 left[i] = 1

在实际代码中，我们先计算出左规则 left 数组，在计算右规则的时候只需要用单个变量维护当前位置的右规则，同时计算答案即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] left = new int[len];
        for (int i = 0; i < len; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int right = 1;
        int res = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (i < len - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            res += Math.max(left[i], right);
        }
        return res;
    }
}