P201. 分糖果

leetcode 135 lintcode 412 贪心 数组 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,n 个小孩站成一条直线,每个小孩都有一个对应的评分。你要根据小孩的评分给他们发糖果,要求每个小孩至少要有一个糖果,并且评分较高的小孩要比相邻的小孩分到更多糖果。你要计算出,至少需要准备多少颗糖果,才能按要求完成分配。

比如说,给你的小孩评分数组是:

[3, 3, 1, 6, 4, 3]

你最少要给这 6 个小孩分配的糖果数量是:

[1, 2, 1, 3, 2, 1]

按照这种分配方法,就可以达到题目要求。因此最少要准备的糖果数量就是这个数组的和,也就是 10。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。