题解 | #分糖果问题#
分糖果问题
http://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352
- 当前孩子的评分比左边的高，也就是递增的，那么当前孩子的糖果数量要比左边个多1。
- 当前孩子的评分等于左边孩子的评分，我们让他降为1,也就是说当前孩子的糖果是1，最 终是不是1,后面还需要在判断。
- 当前孩子的评分低于左边孩子的评分，也就是递减的，这个我们就没法确定当前孩子的糖 果了，但我们可以统计递减孩子的数量（我们可以反向思考，这个递减的序列中，最后一 个肯定是1，并且从后往前都逐渐增加的）
比如数组是[1,3,4,6,8,5,3,1]，8是得分的最高点，8 前面的从1开始都是递增的，8后面的从5开始是递减的。也就是说8前面的从1到6，每个 孩 子 的 糖 果 数 量 分 别 是 [1,2,3,4], 那 么 8 后 面 的 从 5 到 1 每 个 孩 子 的 糖 果 数 量 分 别 是 [3,2,1]。那么8的糖果数量就是左右两边的最大值加1，也就是4+1=5。 所以8左边糖果的数量是(1+4) *4/2=10，右边的糖果数量是(1+3) *3/2=6，所以总的 糖果数量是10+6+5=21。
投递字节跳动等公司8个岗位 >
