LeetCode 面试经典150题---005

#### 135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
本题的意思就是对于数组中的元素i，如果它比i-1大，那么它得到的糖果数就要比i-1大1，对于i+1也是一样的。我们首先将答案数组初始化为全1，然后从左到右遍历，如果此时nums[i]>nums[i-1]，则将res[i] = res[i - 1] + 1；遍历完成后，我们只考虑了每个元素比左边元素要大的情况，因此还需要从右往左遍历一遍，考虑每个元素比右边元素要大的情况，并且由于res[i]已经计算过一遍了，因此第二次遍历的时候不能直接更新res[i]，而是要res[i] = max(res[i], res[i + 1] + 1)，保证res[i]对于左右元素都满足条件。

class Solution {
public:
    int candy(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        int ans = 0;
        for(int i = 1;i < n;i ++ ){
            if(nums[i] > nums[i - 1]) res[i] = res[i - 1] + 1;
        }
        for(int i = n - 2;i >= 0;i -- ){
            if(nums[i] > nums[i + 1]) res[i] = max(res[i], res[i + 1] + 1);
            ans += res[i];
        }
        ans += res[n - 1];
        return ans;
    }
};

定位是困难题，还有一种解法是记忆化搜索，不过不如这个简单，懒得写了，二刷的时候再来查漏补缺吧。