# 135 - Candy

解法一 - 從分數最低的小朋友開始，如果鄰居有比較高分的小朋友就加糖果

這題一開始的思考過程如下：

• 應該先給所有小朋友一顆糖果，然後再看怎麼增加

• 先考慮從左往右掃，如果看到 rating 比隔壁高的就加一顆糖。不過如果rating有從右往左增加的，就無法預估要給到多少顆糖：

  [1,2,3,4,5,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]

  如果從左往右掃，那遇到 20 時只會給他 6 顆糖，但往右得依序遞減，6 顆就不夠了。

• 如果一直從當前 rating 最低的小朋友開始給，好像就可以。所以我們可以用 Priority Queue 記錄當前最低 rating 的小朋友和他的位置。

class rate_pair
{
public:
    int index;
    int rate;

    rate_pair(int id, int r) {
        index = id;
        rate = r;
    }
};

class Compare
{
public:
    bool operator() (rate_pair rate_pair_1, rate_pair rate_pair_2)
    {
        return rate_pair_1.rate > rate_pair_2.rate;
    }
};

class Solution {
public:
    int candy(vector<int>& ratings) {
        // Corner case
        int n = ratings.size();
        if(n < 2) return n;

        // Use a pq to hold ratings 
        priority_queue<rate_pair, std::vector<rate_pair>, Compare> pq;
        for(int i=0; i<n; i++) {
            rate_pair r(i, ratings[i]);
            pq.push(r);
        }

        /*
        while(!pq.empty()) {
            cout << pq.top().index << " " << pq.top().rate << endl;
            pq.pop();
        }
        */

        vector<int> candy(n, 1);

        while(!pq.empty()) {
            int curId = pq.top().index; 
            int curRate = pq.top().rate;
            //cout << curId << " " << curRate << endl;
            pq.pop();

            // If neighbor is higher, add one to neighbor
            int leftId = curId-1, rightId = curId+1;
            if(leftId >= 0 && ratings[leftId] > curRate) candy[leftId] = max(candy[leftId], candy[curId]+1);
            if(rightId < n && ratings[rightId] > curRate) candy[rightId] = max(candy[rightId], candy[curId]+1);
        }

        /*
        cout << "candies: [";
        for(auto c: candy) {
            cout << c << ",";
        }
        cout << "]\n";
        */

        return accumulate(candy.begin(), candy.end(), 0);
    }
};

// idea: use pq to store (rating, index) pair, get min rating kid first, if neightbors have better rating, give the neighbor one more

這個實作的效率非常低落：

Runtime: 64 ms, faster than 9.87% of C++ online submissions for Candy. Memory Usage: 13.3 MB, less than 5.99% of C++ online submissions for Candy.

因為 priority queue 的時間複雜度是 O(nlogn)，所以如果可以用 O(n) 的做法，就可以提升效率。

解法二 - 兩個 array

我們在思考解法一的過程中，有發現到如果只從左邊往右掃，那就可能會無法處理向右遞減比左邊遞增長的例子，所以我們或許可以用兩個 array，一個紀錄從左往右的增加量，一個紀錄從右往左的增加量，最後再取 max 即可。

class Solution {
public:
    int candy(vector<int>& ratings) {
        // Corner case
        int n = ratings.size();
        if(n < 2) return n;

        vector<int> candy(n, 1);

        for(int i=1; i<n; i++) {
            if(ratings[i] > ratings[i-1]) {
                candy[i] = candy[i-1]+1;
            }
        }

        for(int i=n-2; i>=0; i--) {
            if(ratings[i] > ratings[i+1]) {
                candy[i] = max(candy[i], candy[i+1]+1);
            }
        }


        return accumulate(candy.begin(), candy.end(), 0);
    }
};

這樣做的效率就高得多：

Runtime: 28 ms, faster than 78.16% of C++ online submissions for Candy. Memory Usage: 10.7 MB, less than 56.51% of C++ online submissions for Candy.