# [leetcode] Candy

### Candy

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?

tag: greedy

```//版本一，内存超出限制
class Solution {
public:
stack<int> data;
int candy(vector<int> &ratings) {
/*mark backtracking*/
_candy(ratings, 0);
int sum = 0;
while(data.empty() == false){
sum += data.top();
data.pop();
}
return sum;
}
bool _candy(vector<int> ratings, int start){
if(start == 0){
int i = 1;
bool state;
while(true){
data.push(i);
state = _candy(ratings, 1);
if(state == true){
return true;
}
else{
data.pop();
i++;
}
}
}
else if(start == ratings.size()){
return true;
}
else{
int lastCandyNum = data.top();
int min = -1;
int max = -1;
if (ratings[start - 1] > ratings[start]){
max = lastCandyNum - 1;
for(int i = 1; i <= max; i++){
data.push(i);
bool state = _candy(ratings, start + 1);
if(state == true){
return true;
}
else{
data.pop();
}
}
return false;
}
else{
min = lastCandyNum + 1;
while(true){
data.push(min);
bool state = _candy(ratings, start + 1);
if(state == true){
return true;
}
else{
data.pop();
min++;
}
}
}
}
}

};```

```class Solution {
public:
int candy(vector<int> &ratings) {
/*mark backtracking*/
return _candy(ratings, 0, 0);
}
int _candy(vector<int> ratings, int start, int lastCandy){
if(start == 0){
int i = 1;
while(true){
int sum = _candy(ratings, 1, i);
if(sum >= 0){
return sum + i;
}
else{
i++;
}
}
}
else if(start == ratings.size()){
return 0;
}
else{
int min;
int max;
if (ratings[start - 1] > ratings[start]){
max = lastCandy - 1;
for(int i = 1; i <= max; i++){
int sum = _candy(ratings, start + 1, i);
if(sum >= 0){
return sum + i;
}
}
return -1;
}
else{
min = lastCandy + 1;
while(true){
int sum = _candy(ratings, start + 1, min);
if(sum >= 0){
return sum + min;
}
else{
min++;
}
}
}
}
}

};```

calcuateDescendSum()需要借助minPeakVal成员变量。因为peak的值必须比它前一个值大，这个最小值记录在minPeakVal中。

```class Solution {
public:
int minPeakVal = 0;
int candy(vector<int> &ratings) {
/*greedy algorithm... I think it is.*/
if(ratings.size() == 1){
return 1;
}
else{
int descendLength = 0;
int sum = 0;
int lastCandyNum = 0;
for(int i = 0; i < ratings.size(); i++){
if(i == 0){//start
if(ratings[i + 1] >= ratings[i]){//ascending or stable
lastCandyNum = 1;
sum += lastCandyNum;
}
else{//descending
descendLength = 1;
minPeakVal = 0;
}
}
else if(i == ratings.size() - 1){//end
if(ratings[i - 1] > ratings[i]){//descending
descendLength++;
sum += calculateDescendSum(descendLength);
descendLength = 0;
}
else if(ratings[i - 1] < ratings[i]){//ascending
lastCandyNum++;
sum += lastCandyNum;
}
else{//stable
lastCandyNum = 1;
sum += 1;
}
}
else{//non-boundary case
int a = ratings[i - 1];
int b = ratings[i];
int c = ratings[i + 1];
if(b > a && b > c){//peak
minPeakVal = lastCandyNum + 1;
descendLength = 1;
}
else if(b < a && b < c){//bottom
descendLength++;
sum += calculateDescendSum(descendLength);
descendLength = 0;
lastCandyNum = 1;
}
else if(a < b && b < c){//ascending
lastCandyNum++;
sum += lastCandyNum;
}
else if(a > b && b > c){//descending
descendLength++;
}
else{//stable related scenarios
if(a > b){ //a > b && b == c
descendLength++;
sum += calculateDescendSum(descendLength);
descendLength = 0;
lastCandyNum = 1;
}
else if(a < b){//a < b && b == c
lastCandyNum++;
sum += lastCandyNum;
}
else{
if(b < c){//a == b && b < c
lastCandyNum = 1;
sum += lastCandyNum;
}
else if(b > c){//a == b && b > c
minPeakVal = 0;
descendLength = 1;
}
else{//a == b && b == c
lastCandyNum = 1;
sum += lastCandyNum;
}
}
}
}
}
return sum;
}
}
int calculateDescendSum(int num){
int sum = 0;
for(int i = 1; i < num; i++){
sum += i;
}
sum += max(num, minPeakVal);
return sum;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.