Candy

相关题目:

这题考察 observation。

首先尝试了一个 $O(n \log n)$ 的解法,思路:

  1. 构建包含 (rating, index) 的 vector,然后 sort 一下, 复杂度 $O(n \log n)$。
  2. 由于每个 child 拿到的 candy 数量只受到比该 child 的 rating 小的 neighbours 的影响,所以,从低 rating 的 child 开始给糖,每次考虑左右 neigibours 是否已经被给过糖,根据状态判断应该给当前的 child 多少糖。复杂度 $O(n)$。

但是,如果仔细思考,可以发现,对于 children 排列 ---ab--- 而言:

  1. 如果 rating(a) < rating(b)b depends on a but a does not depend on b
  2. 如果 rating(a) = rating(b)ab 没有关系。
  3. 如果 rating(a) > rating(b)a depends on b but b does not depends on a

其中,(1)关系仅向右传递,(3)关系仅向左传递,而且(1)、(3)相互独立。由此,只要两次遍历:

  1. left to right,识别(1)的关系。
  2. right to left,识别(3)的关系。

$O(n)$ 扫完,最后把所有糖数 accumulate 一下,Done。以下是实现:

class Solution {  
public:  
  int candy(vector<int> &ratings) {
    const int n = ratings.size();
    vector<int> nums(n, 1);

    // left to right.
    for (int i = 1; i < n; ++i) {
      if (ratings[i - 1] < ratings[i]) {
        nums[i] = nums[i - 1] + 1;
      }
    }

    // rigth to left.
    for (int i = n - 2; i >= 0; --i) {
      if (ratings[i] > ratings[i + 1]) {
        nums[i] = max(nums[i], nums[i + 1] + 1);
      }
    }

    return accumulate(nums.begin(), nums.end(), 0);
  }
};