LeetCode 135——分发糖果

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1. 题目

2. 解答

初始化左序奖赏全为 1，从左往右遍历，如果右边的人评分比左边高，右边奖赏比左边奖赏增 1。

初始化右序奖赏全为 1，从右往左遍历，如果左边的人评分比右边高，左边奖赏比右边奖赏增 1。

左序奖赏和右序奖赏的最大值就是该孩子的最终奖赏值。

class Solution {

public:

    int candy(vector<int>& ratings) {

        int n = ratings.size();

        vector<int> left_reward(n, 1);

        for (int i = 1; i < n; i++)

        {

            if (ratings[i] > ratings[i-1])    left_reward[i] = left_reward[i-1] + 1;

        }

        vector<int> right_reward(n, 1);

        for (int i = n-2; i >= 0; i--)

        {

            if (ratings[i] > ratings[i+1])    right_reward[i] = right_reward[i+1] + 1;

        }

        int candy = 0;

        for (int i = 0; i < n; i++)

        {

            candy += max(left_reward[i], right_reward[i]);

        }

        return candy;

    }

};