贪心题目：分发糖果

题目

标题和出处

标题：分发糖果

出处：135. 分发糖果

难度

6 级

题目描述

要求

有n \texttt{n}n个孩子站成一排。每个孩子有一个评分，使用整数数组ratings \texttt{ratings}ratings表示。

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

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

返回需要给孩子分发的最少糖果数目。

示例

示例 1：

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

示例 2：

输入：ratings = [1,2,2] \texttt{ratings = [1,2,2]}ratings = [1,2,2]
输出：4 \texttt{4}4
解释：可以分别给第一个、第二个、第三个孩子分发1 \texttt{1}1、2 \texttt{2}2、1 \texttt{1}1颗糖果。
第三个孩子只得到1 \texttt{1}1颗糖果，满足上述两个要求。

数据范围

• n = ratings.length \texttt{n} = \texttt{ratings.length}n=ratings.length
• 1 ≤ n ≤ 2 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{2} \times \texttt{10}^\texttt{4}1≤n≤2×104
• 0 ≤ ratings[i] ≤ 2 × 10 4 \texttt{0} \le \texttt{ratings[i]} \le \texttt{2} \times \texttt{10}^\texttt{4}0≤ratings[i]≤2×104

解法

思路和算法

这道题要求给n nn个孩子分发糖果。用长度为n nn的数组candies \textit{candies}candies表示每个孩子得到的糖果数，则应满足以下两个要求。

• 对于任意0 ≤ i < n 0 \le i < n0≤i<n都有candies [ i ] ≥ 1 \textit{candies}[i] \ge 1candies[i]≥1。

• 对于任意j − i = 1 j - i = 1j−i=1，当ratings [ i ] < ratings [ j ] \textit{ratings}[i] < \textit{ratings}[j]ratings[i]<ratings[j]时应满足candies [ i ] < candies [ j ] \textit{candies}[i] < \textit{candies}[j]candies[i]<candies[j]，当ratings [ i ] > ratings [ j ] \textit{ratings}[i] > \textit{ratings}[j]ratings[i]>ratings[j]时应满足candies [ i ] > candies [ j ] \textit{candies}[i] > \textit{candies}[j]candies[i]>candies[j]。

根据贪心策略，为了使分发的糖果数目最少，应在满足两个要求的情况下最小化分发给每个孩子的糖果数目。

首先将candies \textit{candies}candies中的所有元素初始化为1 11，表示每个孩子至少得到1 11颗糖果，然后正向和反向遍历数组ratings \textit{ratings}ratings各一次，更新candies \textit{candies}candies中的元素。

正向遍历时，对于i > 0 i > 0i>0，执行如下操作。

• 如果ratings [ i ] > ratings [ i − 1 ] \textit{ratings}[i] > \textit{ratings}[i - 1]ratings[i]>ratings[i−1]，则必须满足candies [ i ] > candies [ i − 1 ] \textit{candies}[i] > \textit{candies}[i - 1]candies[i]>candies[i−1]，为了使candies [ i ] \textit{candies}[i]candies[i]最小，将candies [ i ] \textit{candies}[i]candies[i]的值更新为candies [ i − 1 ] + 1 \textit{candies}[i - 1] + 1candies[i−1]+1。

• 如果ratings [ i ] ≤ ratings [ i − 1 ] \textit{ratings}[i] \le \textit{ratings}[i - 1]ratings[i]≤ratings[i−1]，则不需要满足candies [ i ] > candies [ i − 1 ] \textit{candies}[i] > \textit{candies}[i - 1]candies[i]>candies[i−1]，因此candies [ i ] \textit{candies}[i]candies[i]的值保持不变。

正向遍历结束之后，candies \textit{candies}candies中的元素满足条件：对于i > 0 i > 0i>0，如果ratings [ i ] > ratings [ i − 1 ] \textit{ratings}[i] > \textit{ratings}[i - 1]ratings[i]>ratings[i−1]则candies [ i ] > candies [ i − 1 ] \textit{candies}[i] > \textit{candies}[i - 1]candies[i]>candies[i−1]。此时candies \textit{candies}candies中的元素为满足要求的最小元素，将candies \textit{candies}candies中的任意元素减少都无法满足要求，因此第i ii个孩子得到的最少糖果数一定大于等于此时的candies [ i ] \textit{candies}[i]candies[i]。

反向遍历时，candies \textit{candies}candies中的元素不可能减少，对于i < n − 1 i < n - 1i<n−1，执行如下操作。

• 如果ratings [ i ] > ratings [ i + 1 ] \textit{ratings}[i] > \textit{ratings}[i + 1]ratings[i]>ratings[i+1]，则必须满足candies [ i ] > candies [ i + 1 ] \textit{candies}[i] > \textit{candies}[i + 1]candies[i]>candies[i+1]，因此candies [ i ] \textit{candies}[i]candies[i]必须大于等于candies [ i + 1 ] + 1 \textit{candies}[i + 1] + 1candies[i+1]+1，为了使candies [ i ] \textit{candies}[i]candies[i]最小，如果candies [ i ] < candies [ i + 1 ] + 1 \textit{candies}[i] < \textit{candies}[i + 1] + 1candies[i]<candies[i+1]+1则将candies [ i ] \textit{candies}[i]candies[i]的值更新为candies [ i + 1 ] + 1 \textit{candies}[i + 1] + 1candies[i+1]+1。

• 如果ratings [ i ] ≤ ratings [ i + 1 ] \textit{ratings}[i] \le \textit{ratings}[i + 1]ratings[i]≤ratings[i+1]，则不需要满足candies [ i ] > candies [ i + 1 ] \textit{candies}[i] > \textit{candies}[i + 1]candies[i]>candies[i+1]，因此candies [ i ] \textit{candies}[i]candies[i]的值保持不变。

反向遍历结束之后，candies \textit{candies}candies中的元素满足条件：对于i < n − 1 i < n - 1i<n−1，如果ratings [ i ] > ratings [ i + 1 ] \textit{ratings}[i] > \textit{ratings}[i + 1]ratings[i]>ratings[i+1]则candies [ i ] > candies [ i + 1 ] \textit{candies}[i] > \textit{candies}[i + 1]candies[i]>candies[i+1]。此时candies \textit{candies}candies中的元素为满足要求的最小元素，将candies \textit{candies}candies中的任意元素减少都无法满足要求。

两次遍历结束之后，计算candies \textit{candies}candies中的元素之和，即为需要给孩子分发的最少糖果数目。

贪心策略的正确性说明如下。

1. 考虑两个相邻的下标i ii和j jj，j − i = 1 j - i = 1j−i=1，ratings [ i ] \textit{ratings}[i]ratings[i]和ratings [ j ] \textit{ratings}[j]ratings[j]的相对大小关系有以下三种情况。

   • 如果ratings [ i ] = ratings [ j ] \textit{ratings}[i] = \textit{ratings}[j]ratings[i]=ratings[j]则candies [ i ] \textit{candies}[i]candies[i]和candies [ j ] \textit{candies}[j]candies[j]之间的大小关系没有要求。

   • 如果ratings [ i ] < ratings [ j ] \textit{ratings}[i] < \textit{ratings}[j]ratings[i]<ratings[j]，则应满足candies [ i ] < candies [ j ] \textit{candies}[i] < \textit{candies}[j]candies[i]<candies[j]。由于只有在正向遍历时会将ratings [ j ] \textit{ratings}[j]ratings[j]更新为ratings [ i ] + 1 \textit{ratings}[i] + 1ratings[i]+1，在反向遍历时不会更新ratings [ i ] \textit{ratings}[i]ratings[i]，因此一定满足candies [ i ] < candies [ j ] \textit{candies}[i] < \textit{candies}[j]candies[i]<candies[j]。

   • 如果ratings [ i ] > ratings [ j ] \textit{ratings}[i] > \textit{ratings}[j]ratings[i]>ratings[j]，则应满足candies [ i ] > candies [ j ] \textit{candies}[i] > \textit{candies}[j]candies[i]>candies[j]。由于在正向遍历时不会更新ratings [ j ] \textit{ratings}[j]ratings[j]，只有在反向遍历时会将ratings [ i ] \textit{ratings}[i]ratings[i]更新为大于等于ratings [ j ] + 1 \textit{ratings}[j] + 1ratings[j]+1的值，因此一定满足candies [ i ] > candies [ j ] \textit{candies}[i] > \textit{candies}[j]candies[i]>candies[j]。

2. 根据上述分析，每个孩子得到的糖果数是满足两个要求的情况下的最小值，将任何一个孩子得到的糖果数减少都无法满足两个要求。

由于根据贪心策略给每个孩子分发的糖果数满足两个要求且每个孩子得到的糖果数都是满足两个要求的情况下的最小值，因此贪心策略可以得到正确的结果。

代码

classSolution{publicintcandy(int[]ratings){intn=ratings.length;int[]candies=newint[n];Arrays.fill(candies,1);for(inti=1;i<n;i++){if(ratings[i]>ratings[i-1]){candies[i]=candies[i-1]+1;}}for(inti=n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candies[i]=Math.max(candies[i],candies[i+1]+1);}}inttotal=0;for(intnum:candies){total+=num;}returntotal;}}

复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)，其中n nn是数组ratings \textit{ratings}ratings的长度。需要正向和反向遍历数组各一次。

• 空间复杂度：O ( n ) O(n)O(n)，其中n nn是数组ratings \textit{ratings}ratings的长度。需要创建长度为n nn的数组记录每个孩子获得的糖果数。