题目

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

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

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

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

示例 1：

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

示例 2：

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

提示：

  • n == ratings.length
  • 1 <= n <= 2 * 10^4

  • 0 <= ratings[i] <= 2 * 10^4

    解题方法

    贪心

    局部最优：前向和后向分别考虑，从左向右，只要当前节点大于左节点，当前节点值在左节点的基础上加1；从右向左，只要当前节点值大于右侧节点，当前节点值在右侧的基础上加1。
    全局最优：评分高的孩子比相邻评分低的获得的糖果多，整体耗费糖果最少。
    时间复杂度O(n)，空间复杂度O(n)
    C++代码：

    1. class Solution {
    2. public:
    3.   int candy(vector<int>& ratings) {
    4.       int n = ratings.size();
    5.       vector<int> candy(n, 1);
    6.       int sum = 0;
    7.       for(int i=1; i<n; i++) {
    8.           if(ratings[i]>ratings[i-1] && candy[i]<=candy[i-1]) candy[i] = candy[i-1] + 1;
    9.       }
    10.       for(int i=n-2; i>=0; i--) {
    11.           if(ratings[i]>ratings[i+1] && candy[i]<=candy[i+1]) candy[i] = candy[i+1] + 1;
    12.       }
    13.       for(int i : candy)  sum += i;
    15.       return sum;
    16.   }
    17. };

    一次遍历

    将问题转化为对序列中上升、下降序列的处理，对于上升序列（ratings[i] >= ratings[i-1]）记录该序列末尾发放的糖果数；对于下降序列，随着下降序列的长度增加增加该序列中每一个孩子发放的糖果数，当下降序列起始糖果数等于上升序列末尾糖果数时，将上升序列最后一个元素也纳入下降序列。
    时间复杂度O(n)，空间复杂度O(1)
    C++代码：

    1. class Solution {
    2. public:
    3.   int candy(vector<int>& ratings) {
    4.       int n = ratings.size();
    5.       int sum = 1;
    6.       int up_end = 1;
    7.       int down_length = 0;
    8.       int cur = 1;
    9.       for(int i=1; i<n; i++) {
    10.           if(ratings[i]>=ratings[i-1]) {
    11.               down_length = 0;
    12.               cur = ratings[i]==ratings[i-1] ? 1 : cur+1;
    13.               sum += cur;
    14.               up_end = cur;
    15.           }
    16.           else {
    17.               down_length++;
    18.               if(down_length==up_end) down_length++;
    19.               sum += down_length;
    20.               cur = 1;
    21.           }
    22.       }
    24.       return sum;
    25.   }
    26. };