过分谨慎的人难有成就。

题目描述：

分发糖果

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

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

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

解题代码：

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n);
        vector<int> right(n);
        int sum = 0;
        for(int i = 0; i < n; i++){
            if(i != 0 && ratings[i] > ratings[i - 1]){
                left[i] = left[i - 1] + 1;
            }else{
                left[i] = 1;
            }
        }

        for(int i = n - 1; i >= 0; i--){

            if(i != n - 1 && ratings[i] > ratings[i + 1]){
                right[i] = right[i + 1] + 1;
            }else{
                right[i] = 1;
            }
            sum += max(left[i], right[i]);
        }
       return sum;
    }
};

image-20231012212252979

解读与收获：

此题最终满足两个规则，从左到右遍历，每次比较两个孩子，保证如果右边的孩子比左边孩子分高，糖果也要多。从右到左遍历，保证左边的孩子分高，糖果比右边多。简称左规则和右规则。进行两次遍历，第一次遍历从左到右，将满足左规则的糖果分配存放在left数组中。再进行一遍右便利，满足将满足右规则的糖果分配存放到right。同时对比left[i]和right[i]，取其中最大的数，这个数一定同时满足左右规则，累加到sum，最终得到糖果总数。