The two-scanning solution can guarantee the result is optimal? Any proof?


  • 0
    C

    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!


  • 0
    X

    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.


  • 0
    D
    • 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.

    0_1484814259772_peaks.png


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.