题目描述（困难难度）

给 N 个小朋友分糖，每个人至少有一颗糖。并且有一个 数组，如果小朋友的 rating比它旁边小朋友的 rating 大（不包括等于），那么他必须要比对应小朋友的糖多。问至少需要分配多少颗糖。

用 - 表示糖，举几个例子。

解法一

根据题目，首先每个小朋友会至少有一个糖。

如果当前小朋友的 rating 比后一个小朋友的小，那么后一个小朋友的糖肯定是当前小朋友的糖加 1。

比如 ration = [ 5, 6, 7] ，那么三个小朋友的糖就依次是 1 2 3。

如果当前小朋友的 rating 比后一个小朋友的大，那么理论上当前小朋友的糖要比后一个的小朋友的糖多，但此时后一个小朋友的糖还没有确定，怎么办呢？

参考 的解法五，利用正着遍历，再倒着遍历的思想。

首先我们正着遍历一次，只考虑当前小朋友的 rating 比后一个小朋友的小的情况。

接着再倒着遍历依次，继续考虑当前小朋友的 rating 比后一个小朋友的小的情况。因为之前已经更新过一次糖果了，此时后一个小朋友的糖如果已经比当前小朋友的糖多了，就不需要进行更新了。

举个例子

代码的话，我们用一个 candies 数组保存当前的分配情况。

时间复杂度：O（n）。

空间复杂度：O（n）。

解法二

参考 这里。

之前采用了倒着遍历一次的方式进行了解决，这里再考虑另外一种解法。

考虑下边的情况。

对于第 2 个 ，它比后一个 rating 要大，所以要取决于再后边的 rating，一直走到 2，也就是山底，此时对应的糖果数是 1，然后往后走，走回山顶，糖果数一次加 1，也就是到 rating 4 时，糖果数就是 3 了。

再一般化，山顶的糖果数就等于从左边的山底或右边的山底依次加 1 。

所以我们的算法只需要记录山顶，然后再记录下坡的高度，下坡的高度刚好是一个等差序列可以直接用公式求和。而山顶的糖果数，取决于左边山底到山顶和右边山底到山顶的哪个高度大。

而产生山底可以有两种情况，一种是 rating 产生了增加，如上图。还有一种就是 rating 不再降低，而是持平。

知道了上边的想法，基本上就可以写代码了，每个人写出来的应该都不一样，在 discuss 区也看到了很多不同的写法，下边说一下我的思路。

抽象出四种情况，这里的高度不是 rating 进行相减，而是从山底的 rating 到山顶的 经过的次数。

1. 左边山底到山顶的高度大，并且右边山底是平坡。

   

2. 右边山底到山顶的高度大，并且右边山底是平坡。

有了这四种情况就可以写代码了。

我们用 total 变量记录糖果总和， pre 变量记录前一个小朋友的糖果数。如果当前的 rating 比前一个的 rating 大，那么说明在走上坡，可以把前一个小朋友的糖果数加到 total 中，并且更新 pre 为当前小朋友的糖果数。

如果当前的 rating 比前一个的 rating 小，说明开始走下坡，用 down 变量记录连续多少次下降，此时的 pre 记录的就是从左边山底到山底的高度。当出现平坡或上坡的时候，将所有的下坡的糖果数利用等差公式计算。此外根据 pre 和 down 决定山顶的糖果数。

根据当前是上坡还是平坡，来更新 pre。

大框架就是上边的想法了，还有一些边界需要考虑一下，看一下代码。

这个算法相对于解法一的好处就是将空间复杂度从 优化到了 O(1)。

总

解法一虽然空间复杂度大一些，但是很好理解，正着遍历，倒着遍历的思想，每次遇到都印象深刻。解法二主要是对问题进行深入考虑，虽然麻烦些，但空间复杂度确实优化了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情