135. 分发糖果【 力扣(LeetCode) 】

一、题目描述

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

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

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

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

二、测试用例

示例 1：

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

示例 2：

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

三、解题思路

1. 基本思路：
     对于每个孩子来说，他获得的糖果数取决于它的邻居，那就可以分解为两种情况，一种是相对于左邻居来确定他的糖果数，另一种是相对于右邻居来确定他的糖果数，这两种情况要同时满足，则要取两种情况最大的糖果数。【反证法：如果取小的那个，他只能满足一种情况，例如：相对于左邻居，他应该是 4 颗，相对于右邻居，他应该是 5 颗，如果我们取 4 颗，他就无法满足右邻居的情况】
2. 具体思路：
   • 定义相对左右邻居糖果数序列 L 和 R，初始化都为 1 ；定义总糖果数 sum ，初始化为 0 ；
   • 计算左邻居序列：从头到尾，对于第 i 个小朋友来说，如果他比他的左邻居大，那他的糖果数就要比他的左邻居多 1 颗；否则，那他就只有最低的 1 颗糖果。【只有 1 颗糖果才能保证他一定比他的左邻居小，因为每个小朋友最少获得 1 颗】
   • 计算右邻居序列：从尾到头，对于第 i 个小朋友来说，如果他比他的右邻居大，那他的糖果数就要比他的右邻居多 1 颗，否则，那他就只有最低的 1 颗糖果。
   • 计算总糖果数：累加每个小朋友的糖果数，对于第 i 个小朋友来说，他的糖果数要取 L[i] 和 R[i] 最大的一个。【解释：对于每个小朋友来说，他与邻居的关系就四种情况，分别是 L<M<R ，L<M>R ，L>M<R ，L>M>R 。
     • ① L<M<R ：M 的相对左邻居糖果数就是 L+1，相对右邻居糖果数就是 1 ，则 M 的糖果数为 L+1；（满足 L<M ，也满足 M<R ，因为对于 R 来说，他的相对左邻居糖果数是 M+1=L+1+1，相对右邻居不知道，但是取相对左右邻居的最大，所以他的糖果数一定大于等于左邻居糖果数 L+2 。）
     • ② L<M>R ：M 相对 L 和 R 是最大值，最大的最大，肯定是最大，肯定满足 L<M 和 M>R ；
     • ③ L>M<R ：M 相对 L 和 R 是最小值，M 的相对左右邻居糖果数都是 1，所以 M 的糖果数是 1 。【每个小朋友最少分的 1 颗糖果】
     • ④ L>M>R ：第一种情况的方向
       】

四、参考代码

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(n)$

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        vector<int> L(n,1),R(n,1);
        int sum=0;

        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1]){
                L[i]=L[i-1]+1;
            }
            if(ratings[n-i-1]>ratings[n-i]){
                R[n-i-1]=R[n-i]+1;
            }
        }
        for(int i=0;i<n;i++){
            sum+=max(L[i],R[i]);
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21