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

虽然说的是贪婪算法，但我第一个想到的是回溯和动态规划。其实我也不清楚三者的明确区别，不管怎样。能做出来就好。

基本思想，先给第一个孩子一块糖，然后尝试给第二个孩子一块糖，如果不满足条件，则向上层回溯。

暂时来不及写代码，先写到这。占个坑，稍后更新。

版本一，采用回溯算法，用一个stack记录当前状态，如果当前层没有满足条件的解，则返回上一层继续深搜。被Leetcode判为内存超出限额MEMORY LIMIT EXCEEDED。晕，考虑用时间换空间中。

//版本一，内存超出限制
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++;
                    }
                }
            }
        }
    }
    
};

更新：第二版删掉了stack。因为递归中已经隐性地用到stack了，只要在递归函数中多加一个参数便可实现stack的功能。但是，删掉stack后，仍然是内存超限。看来不能用递归了，尝试优化中。

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++;
                    }
                }
            }
        }
    }
    
};

更新：

版本三：AC

贪心算法，每次尝试放入最小的糖果数。空间复杂度O(1)，时间复杂度O(N)。

该题需要分多种情况讨论：

记第i人的rating值为rating[i]，给第i人的糖果数为candy[i]。

则：

如果rating[i]处于上升阶段(rating[i – 1] < rating[i] < rating[i + 1])，则candy[i] = candy[i – 1] + 1.

如果rating[i]处于下降阶段(rating[i – 1] >rating[i] > rating[i + 1])，则此时candy[i]不能确定，需要记录下该下降阶段的总长度，最后用calculateDescendSum()一起求出。

如果rating[i]处于极大值，处于极小值，或rating[i]与相邻的某一元素相等，都要分情况讨论。

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

感觉，根据一个序列的大小变化来求某一相关的值（比如此题，或何时卖股票收益最大问题等等），都可以用贪心或动态规划来实现。并不一定非要用到stack。以减少空间。

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;
    }
};