Leetcode 135. Candy

题目

135. Candy

Difficulty: Hard
Total Accepted: 87.48K
Total Submissions: 330.65K

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

解题报告

AC 截图

题目大意

本题给出一个等级队列，要求队列中每个孩子的糖果都至少为 1 个，且相邻的两个孩子中，等级较高者的糖果数较多。

解题思路

我们可以将问题化为一个个子问题来看，再用贪心策略去解决每个子问题即可。更细节地讲，我们把问题分解为对于任意一个孩子，求他最小糖果数的问题。那么这个问题是简单的，我们只需要检查其左边和右边的孩子的糖果数和等级即可。对于没有计算的孩子，我们以 0 标识；而对于计算过的孩子，我们则直接存储它的糖果数。这样一来，我们就避免了许多重复的计算。应用上面的思路，我们就有了下面的题解：

题解1（最优解）

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    size_t size;
    int result = 0;

    int candy(vector<int>& ratings) {
      vector<int> candies(size = ratings.size(), 0);
      for (int i = 0; i < size; ++i) {
        result += getCandy(ratings, candies, i);
      }
      return result;
    }

    int getCandy(vector<int>& ratings, vector<int>& candies, int index) {
      if (candies[index]) return candies[index];

      if (index > 0 && ratings[index - 1] < ratings[index]) {
        if (index < size - 1 && ratings[index + 1] < ratings[index]) {
          return candies[index] = (max(candies[index - 1], getCandy(ratings, candies, index + 1)) + 1);
        }
        else {
          return candies[index] = (candies[index - 1] + 1);
        }
      }
      else {
        if (index < size - 1 && ratings[index + 1] < ratings[index]) {
          return candies[index] = (getCandy(ratings, candies, index + 1) + 1);
        }
        else {
          return candies[index] = 1;
        }
      }
    }
};