[力扣题解]135. 分发糖果

[困难] 题目：135. 分发糖果

思路

贪心法

代码

// 贪心
// Step 1 : 从左往右
// Step 2 : 从右往左
class Solution {
public:
    int candy(vector<int>& ratings) {

        int i, size = ratings.size(), sum = 0;
        vector<int> candy(size, 1); // 基础是1个

        for(i = 0; i < size-1; i++)
        {
            // 右边孩子分高些
            if(ratings[i] < ratings[i+1])
            {
                // 从左往右，依据左边
                candy[i+1] = candy[i] + 1;
            }
        
        }
        
        for(i = size-1; i > 0; i--)
        {
            if(ratings[i-1] > ratings[i])
            {
                // 从右往左，依据右边
                candy[i-1] = max(candy[i] + 1, candy[i-1]);
                // 为什么要用 max 呢？
                
            }
        }
        
        for(i = 0; i < size; i++)
        {
            sum += candy[i];
        }
        return sum;
    }
};

• （1）为什么第一次for循环从左到右，下一次从右到左？
  这两次for循环方向相反，有一点像动态规划。从左到右是因为比较的时候要用到左边的元素，所以从左到右，从右到左同理；
• （2）为什么要用max？
  因为不这样，上一个从左到右的for就白费了，要保证既大于右边的（上一次for循环比较的结果不能丢），又大于左边的（这次比较的结果）