博文中会简要介绍Leetcode P0135题目分析及解题思路。
“Candy”这道题不算特别难，主要考察的是贪心算法。这道题利用贪心算法可以在O(n)的时间复杂度内得到结果。
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.
这道题贪心算法的思路其实很简单，围绕的核心是尽可能给指定的孩子最少的糖。有如下三种情况，
首先第一个孩子至少要拿到1个糖果，所以先给candies[0]赋值为1，
-
若当前rating和上一个rating一样，则根据贪心算法原则，尽可能给最少的糖果，则给1个糖果。
-
若当前rating比上一个大，则根据贪心算法的原则，只给出比上一个孩子多1个的糖果。
-
若当前rating比上一个小（核心情况），此时我们需要记录当前单调递减序列的长度，根据贪心的原则，我们将会在持有最小rating的孩子那里给出1个糖果，那么当我们知道完整的递减序列后，就可以逆向得到这个递减序列上的每个人最少应持有的糖果个数。
一旦递减序列长度不为零，但是遇到了前两种情况或者遍历结束，我们则开始计算这个递减序列所需要的最少糖果个数。首先是判断递减序列的最左起点的糖果数目是否满足要求，若低于最少糖果需求，则补足，否则不变，然后计算剩余递减序列的最少糖果需求即可。
以下是Java的题解代码实现。
class Solution {
public int candy(int[] ratings) {
int N = ratings.length;
if (N == 0)
return 0;
int total = 1, decreasingLen = 0;
int[] candies = new int[N];
candies[0] = 1;
for (int itr=1; itr<N; ++itr) {
if (ratings[itr] == ratings[itr-1]) {
candies[itr] = 1;
// Calculate the addition to the former decreasing sequence
if (decreasingLen > 0) {
total += this.calculate(decreasingLen, candies, itr);
decreasingLen = 0;
}
total += candies[itr];
}
else if (ratings[itr] > ratings[itr-1]) {
candies[itr] = candies[itr-1]+1;
// Calculate the addition to the former decreasing sequence
if (decreasingLen > 0) {
total += this.calculate(decreasingLen, candies, itr);
decreasingLen = 0;
}
total += candies[itr];
}
else {
++decreasingLen;
candies[itr] = 1;
}
}
// Calculate the addition to the former decreasing sequence
if (decreasingLen > 0) {
total += this.calculate(decreasingLen, candies, N);
decreasingLen = 0;
}
return total;
}
private int calculate(int len, int[] candies, int itr) {
int begin = 1+len, sum = 0;
if (candies[itr-1-len] < begin)
sum += (begin-candies[itr-len-1]);
sum += (1+len)*len/2;
return sum;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int candy(vector<int>& ratings) {
int N = ratings.size();
if (N == 0)
return 0;
int total = 1, decreasing_len = 0;
int *candies = new int[N];
candies[0] = 1;
for (int itr=1; itr<N; ++itr) {
if (ratings[itr] == ratings[itr-1]) {
candies[itr] = 1;
// Calculate the addition to the former decreasing sequence
if (decreasing_len > 0) {
total += _Calculate(decreasing_len, candies, itr);
decreasing_len = 0;
}
total += candies[itr];
}
else if (ratings[itr] > ratings[itr-1]) {
candies[itr] = candies[itr-1]+1;
// Calculate the addition to the former decreasing sequence
if (decreasing_len > 0) {
total += _Calculate(decreasing_len, candies, itr);
decreasing_len = 0;
}
total += candies[itr];
}
else {
++decreasing_len;
candies[itr] = 1;
}
}
// Calculate the addition to the former decreasing sequence
if (decreasing_len > 0) {
total += _Calculate(decreasing_len, candies, N);
decreasing_len = 0;
}
return total;
}
private:
int _Calculate(int len, int *&candies, int itr) {
int begin = 1+len, sum = 0;
if (candies[itr-1-len] < begin)
sum += (begin-candies[itr-len-1]);
sum += (1+len)*len/2;
return sum;
}
};