of course. The purpose of this question is to make a O(nlogn) time complexity, O(n) space sort, which means heap sort.
Posts made by xzckiller
RE: Simple DP 8ms Solution for Best Time to Buy and Sell Stock III
But how you do guarantee the exclusive transactions?
RE: The two-scanning solution can guarantee the result is optimal? Any proof?
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.
RE: Do neighboring children with equal rating get unequal candies
Case 2 [1,2,2] shall give 4 candies, as [1,2,1].
It suffices (1) everyone gets a candy
(2) the one who has higher rate has more candies than neighbors.
Equal rate does not mean higher rate.
RE: Share my O(1) space O(n) time C++ solution with detailed explanation
Good code. One thing to point out here is that you don't need to specialize some codes for the first row since i=0, so the step size is 2 * (numRows - 1 - 0).