分发糖果

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

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

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

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

初始化数组vector<int>t(n,1)存储每个孩子的糖果数量。

分两次遍历数组

  1. 从左到右遍历数组，使得右边孩子的评分数大于左边孩子评分数，则右边孩子糖果数比左边孩子多1。

  2. 从右到左遍历数组，如果左边孩子的评分数大于右边孩子评分数，则左边孩子糖果数等于max(t[i],t[i+1]+1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        vector<int>t(n,1);
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1])
                t[i]=t[i-1]+1;
        }
        for(int i=n-2;i>-1;i--){
            if(ratings[i]>ratings[i+1])
                t[i]=max(t[i+1]+1,t[i]);
        }
        int count=0;
        for(int i:t) count+=i;
        return count;
    }
};