LeetCode #135：Candy Distribution(分发糖果)

题目描述

本题需要把整个问题一分为二去看。先确定右边孩子的评分大于左边的情况，即顺序遍历 ratings 数组，只要右边孩子的评分比左边大，右边孩子就多一个糖果（局部最优），从而使得相邻的孩子中，评分高的右孩子都能相对左孩子多获得一颗糖；同理再倒序遍历 ratings 数组，使得左边孩子的评分高于右边孩子时，多给一颗糖。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candys(n, 1); // 糖果分配数组，初始化全1代表每个孩子至少分配一颗糖
        for(int i = 1; i < n; i ++) {
            if(ratings[i] > ratings[i - 1]) // 从左往右看，右边孩子的评分高于左边孩子时，多给一颗糖
                candys[i] = candys[i - 1] + 1;            
        }
        for(int i = n - 2; i >= 0; i --) {
            if(ratings[i] > ratings[i + 1]) // 从右往左看，左边孩子的评分高于右边孩子时，多给一颗糖，并与老的值取最大（这样才能保证当前孩子的糖数既大于左边孩子又大于右边孩子）
                candys[i] = max(candys[i], candys[i + 1] + 1);       
        }

        int res = 0;
        for(int i = 0; i < n; i ++) // 求糖果分配数组的和得出最终答案
            res += candys[i];

        return res;
    }
};