Leetcode 135. 分发糖果

Leetcode 135. 分发糖果

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目

思路

• 将所有孩子分到的糖果初始化为1，每一个孩子最少分到一个糖果

• 先确定右边的元素大于左边的元素情况，从左向右开始遍历，如果ratings[i + 1] > ratings[i], 那么之后ratings[i + 1] = ratings[i] + 1

• 在确定左边的元素大于右边的元素，如果ratings[i] > ratings[i + 1], 那么ratings[i] = ratings[i + 1] + 1, 但是由于左边的孩子分到的糖果还要大于他左边的孩子分到的糖果，所以必须写成ratings[i] = max(ratings[i + 1] + 1,ratings[i])

举一个例子：5 7 8 3, 首先初始化成：1 1 1 1， 之后从左边开始遍历，结果是：1 2 3 1 然后从右边开始遍历：如果不考虑从左往右遍历过的结果，那么就是1 1 2 1（但是7 > 5 7的糖果必须大于5的糖果，不成立），如果考虑，结果就是1 2 3 1

代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candySum(ratings.size(),1);

 
        // 从左向右
        for(int i= 0; i < candySum.size() - 1; i++)
        {
            // 右边的评分比左边要高
            if(ratings[i + 1] > ratings[i])
            {
                candySum[i+1] = candySum[i] + 1;
            }
        }

        // 从右向左
        for(int i = candySum.size() - 2; i >= 0; i--)
        {
            // 左边的评分比右边要高
            if(ratings[i] > ratings[i + 1])
            {
                // 此时的candySum[i] 已经是从左到右遍历一遍的结果了 但是与要求比右边的要大
                // 所以综合结果 取最大值
                candySum[i] = max(candySum[i + 1] + 1,candySum[i]);
            }
        }

        // 统计结果
        int result = 0;
        for(int i = 0; i < candySum.size(); i++)
        {
            result += candySum[i];
        }

        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39