leetcode 链接：135. 分发糖果

题目

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

  • 每个孩子至少分配到 1 个糖果。
  • 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

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

示例：

  1. 输入：[1,0,2]
  2. 输出：5
  3. 解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

解答 & 代码

解法一：正逆序两次遍历

由题意，分发糖果的规则是：评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果，且每个孩子至少分配到 1 个糖果。
因此，可以将规则拆解为：

  • 从左往右遍历数组，
    • 如果 ratings[i] > ratings[i - 1]，则 i 号学生分的糖果数量应该比 i - 1 号学生多，因为求最小值，所以 i 号学生分的糖果数 left[i] = left[i - 1] + 1
    • 否则给第 i 个学生分一个糖果，即 left[i] = 1
  • 从右往左遍历数组
    • 如果 ratings[i] > ratings[i + 1]，则 i 号学生分的糖果数量应该比 i + 1 号学生多，因为求最小值，所以 i 号学生分的糖果数 right[i] = right[i - 1] + 1
    • 否则给第 i 个学生分一个糖果，即 right[i] = 1

对于每个学生 i，两次遍历得到的 left[i] 和 right[i] 的最大值就是其最少应分得的糖果数量

另外，从右往左遍历的过程可以不使用 right 数组存储，因为 right[i] 只和 right[i+1] 有关，因此使用一个 right 变量即可。并且在从右往左遍历的过程中，就可以直接比较 left[i] 和当前 right 的最大值，加入到糖果总数的计数 totalCandy 中

  • 时间复杂度 O(N)

  • 空间复杂度 O(N)

    class Solution {
public:
  int candy(vector<int>& ratings) {
      int size = ratings.size();
      // 从左往右遍历数组，计算每个学生所需分的最小糖果数，存储在 left 数组中
      vector<int> left(size, 1);
      for(int i = 1; i < size; ++i)
      {
          // 如果当前学生的评分比前一个学生高，则分的糖果数比前一个学生多一个
          if(ratings[i] > ratings[i - 1])
              left[i] = left[i - 1] + 1;
          // 否则，给当前学生分一个糖果即可
          else
              left[i] = 1;
      }

      int totalCandy = 0;        // 需要分的糖果总数
      // 从右往左遍历数组，计算每个学生所需分的最小糖果数，记为 right
      int right = 1;
      totalCandy += max(left[size - 1], right);
      for(int i = size - 2; i >= 0; --i)
      {
          // 如果当前学生的评分比后一个学生高，则分的糖果数比后一个学生多一个
          if(ratings[i] > ratings[i + 1])
              ++right;
          // 否则，给当前学生分一个糖果即可
          else
              right = 1;

          // 比较两次遍历该学生需要分的糖果数，取最大值，加入结果计数中
          totalCandy += max(left[i], right);
      }
      return totalCandy;
  }
};

    执行结果： ``` 执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 98.80% 的用户 内存消耗：17.3 MB, 在所有 C++ 提交中击败了 35.31% 的用户


<a name="wcwag"></a>
## 解法二：一次遍历
时间复杂度 O(N)，空间复杂度 O(1)
```cpp
class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        int inc = 1;    // 递增序列最右边的人（即分糖果分的最多的人）分的糖果数
        int dec = 0;    // 递减序列的长度
        int pre = 1;    // 前一个人分的糖果数
        int totalCandy = pre;    // 总的糖果数
        // 一次遍历
        for(int i = 1; i < size; ++i)
        {
            // 如果当前学生的评分不低于前一个学生，则仍处于递增序列
            if(ratings[i] >= ratings[i - 1])
            {
                // 当前学生分的糖果数：如果评分和前一个学生相同，则分一个就够了，否则分 pre + 1 个
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                // 更新总的糖果数
                totalCandy += pre;
                // 更新递增序列分的糖果数的最大值
                inc = pre;
                // 递减序列长度为 0
                dec = 0;
            }
            else
            {
                // 递减序列长度 +1
                ++dec;
                // 如果递减序列长度 = 递增序列的最大值。需要把递增序列的最后一个也算到递减序列中
                // 因此递减序列长度 +1
                if(dec == inc)
                    ++dec;
                // 更新糖果总数
                // 递减序列加的糖果数依次是 1、2、3...
                // 实际上递减序列应该分的糖果数依次是 ...、3、2、1
                // 但效果是一样的
                totalCandy += dec;
                // 更新前一个人分的糖果数为 1（即当前学生分的糖果数）
                pre = 1;
            }
        }
        return totalCandy;
    }
};

执行结果：

执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 78.67% 的用户
内存消耗：16.7 MB, 在所有 C++ 提交中击败了 97.55% 的用户