candy的方法证明

https://leetcode.com/problems/candy/
candy这道题，要求ratings比邻居高的小朋友得到更多的糖果。ratings和邻居相等，则多少无所谓。每人至少一颗糖果，问最少需要多少糖果。
为什么遍历两遍的算法能保证结果是最小的，怎么证明？

把所有小朋友的rating看做一条波形曲线，那么
1. 第一次从左向右遍历时，记录的Candy数其实是当前最大上升沿的长度；
2. 第二次从右向左遍历时，记录的Candy数其实是当前最大逆上升沿（从右向左看）的长度。
所以：
1. 在波谷处，左右两次遍历的结果必然都是1，因此波谷处小朋友得到的糖果一定是1。显然最优。
2. 在波峰处，假设左上升沿长度较大，那么波峰处小朋友得到的糖果如果小于左上升沿长度，那么左上升沿一侧一定会有至少两个小朋友无法分配；右侧同理。所以该算法得到的max（左上升沿长度，右下降沿长度）在波峰处也是最优。
3. 在非波峰波谷的上升沿处，采用的仅是第一次左->右遍历的结果，即左上升沿长度。同2，如果分配糖果数小于此值，那么左侧必然有两个小朋友无法分配。因此该值必定最优。
4. 在非波峰波谷的下降沿处，类似3，结果同样最优。
5. rating与左右都相等的情况，同1.

综合上述条件来看，在任何一点都不可能找到比该算法更优的结果，因此该算法（如果是正确的）结果必定最优。

我也是西浦的可我等级不够不能加你好友，想问你最后去了哪所学校啊！

秋水有爱 发表于 2016-2-17 15:22
我也是西浦的可我等级不够不能加你好友，想问你最后去了哪所学校啊！

西浦是哪里？我没有去过，我是杭州的。

大成若缺 发表于 2016-2-18 05:45
西浦是哪里？我没有去过，我是杭州的。

好吧，我看到你的一个帖子说你本科是xjtlu的...可能是我弄错了，不好意思啊...
不过你去SIT了吗？

秋水有爱 发表于 2016-2-18 15:30
好吧，我看到你的一个帖子说你本科是xjtlu的...可能是我弄错了，不好意思啊...
不过你去SIT了吗？

你又要再说一次不好意思了
你也可以再去一个随机的帖子下面问楼主，你去sit吗？