分发糖果

分析

这道题难道中等。核心问题在于如何正确处理两种情况：

比左边的人分数高
比右边的人分数高

为了解决这个问题。我们可以进行两次遍历，一次从左往右遍历且只考虑情况 1，一次从右往左遍历且只考虑情况 2。在从右往左便利的过程中，比较当前结果和从左往右遍历至当前位置的结果，取最大值。这样，我们就能保证时间复杂度和空间复杂度均为 $O(2N) =$ O(N)$。

那有没有更好的办法呢？我们可以从情况 1 的角度考虑：如果当前分数大于等于左边人的分数，那证明此时我们处于一个递增的序列当中。那我们可以采用上一个题从左往右便利的思路去做, 使用变量 pre 来记录上一个人所分的糖果数，用变量 inc 来记录当前递增序列的长度。那么当不满足情况 1 的时候，那证明我们在递减序列中。我们可以定义一个变量 des 。通过 des++ 来记录当前递减序列的长度。

现在有个新的问题：假设存在这么一个数列： $[1, 3, 2, 1]$ ，且我们已经给第一位分配了一颗糖果。现在我们开始遍历：

当 idx = 3 时，因为 $3 > 1$ ，所以我们给第二位分配两颗糖果。
当 idx = 2 时，因为 $2 < 3$ ，所以我们给第三位分配一颗糖果。
当 idx = 1 时，因为 $1 < 2$ ，所以我们给第四位分配 award[2] - 1 颗糖果。但根据第二步， $\mathrm{award}[2] = 1$ ，所以不符合题意。

那么我们该怎么修复这个 bug 呢？

回想一下，我们定义了一些变量：pre, inc, dec. pre 是用来记录上一个人分的糖果，在递增序列中我们要给当前人分配 pre + 1 个糖果。 inc 用于记录当前递增序列的长度，同样也是当前序列的最大值。 dec 用于记录递减序列的长度。现在我们分三种情况情况来考虑：

$\mathrm{rating}[\mathrm{idx}] > \mathrm{rating}[\mathrm{idx} - 1]$ 。此时我们处于递增的序列当中，在递增序列中我们要给当前人分配 pre + 1 个糖果。因此 inc 与 pre 需要自增。
$\mathrm{rating}[\mathrm{idx}] = \mathrm{rating}[\mathrm{idx} - 1]$ 。此时我们处于一个序列的断裂点。因此 inc 和 pre 都会被重置为 1。
$\mathrm{rating}[\mathrm{idx}] < \mathrm{rating}[\mathrm{idx} - 1]$ $rating [idx] < rating [idx - 1]$ 。此时我们处于一个递减序列当中。因为 dec 是个变量，所以我们不需要严格遵守「有序地求出从左往右对应糖果数量」。在分配之前，我们先让 dec++，然后做以下判断：
- 如果 $\mathrm{dec} < \mathrm{inc}$ ，那么证明此时我们处于一个比前一个序列短的递减序列中。当前人所分的糖果就是自增后的 dec。
- 如果 $\mathrm{dec} = \mathrm{inc}$ ，那么此时递减序列的长度与递增序列相等。就像例子中的最后一项一样。这时我们应该在 dec++ 的基础上再次 dec++。第一次的自增和上述情况一样，是表示当前人所分的糖果数。再次自增则保证了 rating 数组最大值的人能得到最多的糖果。

此时为了维护 des，我们需要在非递减序列中令 des = 0。从而保证 des 不会大于 inc，即保证不会超过 rating 数组最大值的人能得到最多的糖果。

解答

class Solution {
public:
  int candy(vector<int> &ratings) {
    auto n = ratings.size();
    auto ans = 1;
    auto inc = 1;
    auto dec = 0;
    auto pre = 1;

    for (auto i = 1; i < n; ++i) {
      if (ratings[i] >= ratings[i - 1]) {
        dec = 0;
        pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
        ans += pre;
        inc = pre;
      } else {
        dec++;
        if (dec == inc)
          dec++;
        pre = 1;
        ans += dec;
      }
    }

    return ans;
  }
};