After reading the twoscanning solution to this question several times, I still cannot make myself sure that the result is optimal. Could anyone give a strict proof to it? Thanks!
The twoscanning solution can guarantee the result is optimal? Any proof?

The two scan method is not elegant but it is easy to prove.
Assume after twoscan method, there is one kid has higher rate than his/her neighbor but get less candies, say k.
ratings[k] > rating[k1] && rating[k] > rating[k+1]
If k gets less candies than k1, it violates the first pass that if ratings[k] > rating[k1] then candy[k]=candy[k1]+1.
If k gets less candies than k+1, it violates the second pass that if ratings[k] > rating[k+1] then candy[k]=max(candy[k], candy[k+1]+1).
Thus, k does not get less candies than both of his neighbors. The assumption does not valid. The solution is proved.

 Use the height of rectangles to represent the number of candies that the kids get. We will get a lot of peaks.
 Every peak is independent. So we can divide the candy distribution into independent peaks.
 We can prove that the construction of a single peak is optimal, we can prove the whole candy distribution is optimal.
 It’s easy to prove every single peak is optimal.