LeetCode135 分发糖果

• 题目描述

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

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

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

链接：https://leetcode.cn/problems/candy

• 示例

输入：ratings = [1,0,2]

输出：5

解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

• 算法思想

本题的难点在于贪心策略的选择，对于糖果的分发，设置一个数组res存储每个孩子得到的糖果，初始值设为1，之后从左向右遍历数组ratings，若右边ratings[i]评分大，则res[i]=res[i-1]+1,然后从右向左遍历数组ratings，若左边ratings[i]评分大，则res[i]=max(res[i]，res[i+1]+1)【这么做是为了防止有这样一种情况：从左至右遍历数组ratings时，ratings[i]评分大，则res[i]=res[i-1]+1，而res[i+1]+1可能比res[i-1]+1小，若不取最大值，则糖果的分发可能会比实际的少】。最后将res数组的元素相加即可得到最少糖果数目 。

• 代码

 1 class Solution {
 2 public:
 3     int candy(vector<int>& ratings) {
 4         int n=ratings.size();
 5         vector <int>res(n,1);
 6         for(int i=1;i<ratings.size();i++){//右边大
 7             if(ratings[i]>ratings[i-1])
 8             res[i]=res[i-1]+1;   
 9         }
10         for(int i=ratings.size()-2;i>=0;i--){//左边大
11             if(ratings[i]>ratings[i+1])
12             res[i]=max(res[i],res[i+1]+1);//注意此时要考虑res[i]也大于右边的情况，故取一个max
13         }
14         //统计总和
15         int nums=0;
16         for(int i=0;i<res.size();i++)
17                nums+=res[i];
18         return nums;
19     }
20 };