空間復(fù)雜度O(n)
class Solution {
public:
/**
* @param ratings Children's ratings
* @return the minimum candies you must give
*/
int candy(vector<int>& ratings) {
// Write your code here
vector<int> dp(ratings.size(), 1);
for(int i = 1; i < dp.size(); ++i){
if(ratings[i] > ratings[i-1]){
dp[i] = max(dp[i], dp[i-1] + 1);
}
}
for(int i = dp.size() - 1; i > 0; --i){
if(ratings[i] < ratings[i-1]){
dp[i-1] = max(dp[i-1], dp[i] + 1);
}
}
return accumulate(dp.begin(), dp.end(), 0);
}
};
空間復(fù)雜度O(1)
class Solution {
public:
/**
* @param ratings Children's ratings
* @return the minimum candies you must give
*/
int candy(vector<int>& ratings) {
// Write your code here
int total = 0;
int preCount = 1; //前一個小孩的糖果數(shù)
int descendStartCount = preCount; //遞減序列開始的孩子的糖果數(shù)
int length = 0;
if(ratings.size() == 0) {
return 0;
}
total++;
for(int i = 1; i < ratings.size(); ++i) {
if(ratings[i] < ratings[i-1]) {
length ++ ;
if(descendStartCount <= length) {
total++; //根據(jù)遞減序列的長度修正遞減序列第一個孩子的糖果數(shù)
}
total += length; //逆序獲取后續(xù)孩子的糖果數(shù)
preCount = 1; //注意
}else{
int currentCount = 0;
if(ratings[i] > ratings[i-1]) {
currentCount = preCount + 1;
}else{
currentCount = 1;
}
total += currentCount;
preCount = currentCount;
length = 0; //注意
descendStartCount = currentCount;
}
}
return total;
}
};
