题解 | #分糖果问题#

贪心：两次扫描分发糖果

1. 左边比右边大，从后往前扫描（否则无法用前面的糖果数量更新后面的糖果数量）

2. 右边比左边大，从前往后扫描

最后统计总糖果数量

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        int n = arr.size();
        vector<int> candy(n, 1);
        // 右边比左边分数大的情况
        for (int i = 1; i < n; i ++ ) {
            if (arr[i] > arr[i - 1])
                candy[i] = candy[i - 1] + 1;
        }
        // 左边比右边大的情况
        for (int i = n - 2; i >= 0; i -- ) {
            if (arr[i] > arr[i + 1]) 
                candy[i] = max(candy[i], candy[i + 1]  + 1);
        }
        
        int res = 0;
        for (auto x : candy) res += x;
        return res;
    }
};