135. Candy

https://leetcode.com/problems/candy/

给定一个数组，要求给每个index分配candy，candy不得低于1并且元素值比左右高的分得糖不得少于左右。先从左往右，如果rating比左边大就设成左边的值+1, 否则就设成1。这样左边就满足了。再类似右往左做，并把i的值设为两趟中最大的，右边和左边都满足了。

/*
 * @lc app=leetcode id=135 lang=cpp
 *
 * [135] Candy
 */
class Solution {
public:
    int candy(vector<int>& ratings) {
        const int N = ratings.size();
        int res = 0;
        vector<int> r(N);
        for (int i = 0; i < N; ++i) {
            if (i > 0 && (ratings[i] > ratings[i - 1])) r[i] = r[i - 1] + 1;  
            else r[i] = 1;
        }
        for (int i = N - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) r[i] = max(r[i], r[i + 1] + 1);  
        }
        for (const auto i : r) {
            res += i;
        }
        return res; 
    }
};