After reading the two-scanning 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 two scan method is not elegant but it is easy to prove.
Assume after two-scan method, there is one kid has higher rate than his/her neighbor but get less candies, say k.
ratings[k] > rating[k-1] && rating[k] > rating[k+1]
If k gets less candies than k-1, it violates the first pass that if ratings[k] > rating[k-1] then candy[k]=candy[k-1]+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.