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;
    }
};

发表回复

您的电子邮箱地址不会被公开。