leetcode每日一道（14）按评分给小朋友分糖果

leetcode每日一道（14）按评分给小朋友分糖果

题目描述

有N个小朋友站在一排，每个小朋友都有一个评分
你现在要按以下的规则给孩子们分糖果：
每个小朋友至少要分得一颗糖果
分数高的小朋友要他比旁边得分低的小朋友分得的糖果多
你最少要分发多少颗糖果？

思路

这样一道题有点意思，经过分析可知，为使得糖果数目尽可能少，用一个vector数组来存储糖果数目，每个小旁友的初始值置为1，如果一个小旁友的左右都是比他得分高的，那么不用说，他一定是拿一个糖果。那么如果一个小旁友比他左边的得分高，他势必要比左边的多一个糖果，但是同时他又比右边的小旁友得分高，那么他也要比右边的小旁友多一个糖果，到底是多少个糖果，这就要考虑，是他左边连续的高人数多，还是右边连续高的人数多，然后得取较大值。
因此，这道题要得到数组每个值，只需要正向扫描一次，反向扫描一次，就可以了。

代码

class Solution {
public:int candy(vector<int> &ratings) {int num = ratings.size();int s=0;if (num==1) return 1;vector<int> dp(num,1);for (int i=0; i<num-1;i++){if (ratings[i]<ratings[i+1]) dp[i+1] =dp[i]+1;}for (int i=num-1; i>0;i--){if (ratings[i-1]>ratings[i]) dp[i-1] = max(dp[i-1],dp[i]+1);}for (int i=0;i<num;i++){s += dp[i];}return s;}
};