###糖果分析
####原题 N个孩子站成一排，每个人分给一个权重。按照如下的规则分配糖果：
- 每个孩子至少有一个糖果
- 所分配权重较高的孩子，会比他的邻居获得更多的糖果
问题是，最少需要多少个糖果？
####分析 这个题目是要求找到最少需要多少个糖果。最少的糖果是存在的，体现在哪里呢？权重较高的孩子，会比他的邻居们获得更多的糖果，那么多多少呢？可以是1个，2个，或者更多个，但显然，当多一个的时候。总的糖果的数量是最少的，除此之外呢？当某一个孩子的邻居的权重都比他大，那他应该获得多少个糖果呢？只有一个——每个孩子至少要得到一个。
所以根据上面的分析，我们可以想办法找到权重数组A中的波谷（也就是权重小于邻居们的孩子），很显然这些孩子每人只可以分得一个糖果。我们开辟一个新的数组B，表示每个孩子可以得到的最少的糖果数。扫描一遍A，得到所有的波谷的孩子，然后将对应的B的值设置为1.对于第一个和最后一个权重，只要A[0]<A[1]，以及A[n-1]<A[n-2]，就认为A[0]和A[n-1]是波谷，这里假设数组A的元素个数为n。
然后该如何确定其他孩子的糖果数呢？我们看一个具体的例子，来更加形象的说明如何求得。如下表：
| A | 1 | 2 | 3 | 4 | 2 | 6 |
| B | 1 | 1 |
现在已经确定B中两个孩子的最少糖果数，然后：
- B[0]=1，那么B[1]=2,B[2]=3,B[3]=4，是一定的。原因是要满足题目中的第2个条件。
- 同理，B[5]=2。
- 上面的是按照数据的正向看的，如果逆向，则B[3]=2,因为B[4]=1。这时，出现了冲突，要满足最少的糖果数，似乎要取B[3]=2，但是不满足条件2.所以遇到这个情况，则选取较大的。得到表格如下：
| A | 1 | 2 | 3 | 4 | 2 | 6 |
| B | 1 | 2 | 3 | 4 | 1 | 2 |
则最少糖果数为(1+2+3+4+1+2) = 13个。
总结算法步骤如下：
- 找到数组的波谷，将波谷的孩子的糖果数设置为1.此步：时间复杂度O(n)，空间复杂度O(n)
- 从左到右遍历数组，从每一个1开始，其后的孩子的糖果比前一个孩子多1个。此步：时间复杂度O(n)
- 从右向左遍历数组，从每一个1开始，其后的孩子的糖果比前一个孩子多1个。波峰的孩子，取最大的糖果个数。
- B数组每一个元素求和，即可得到最少需要的糖果数。
整体算法的时间复杂度为O(n)，空间复杂度为O(n)。进一步优化，可以将找波谷的一次循环省略。
【分析完毕】