Solution to Hills

7 Sep

Question Name: Hills

Question Description: An integer array store the heights of some consecutive hills. Find a minimum integer N, so that you could increase/decrease the heights of the hills by any integer in range [0, N]. After the adjustment, the heights of these hills should be in a strickly increasing order (PS: [3, 3, 4] is NOT strictly increasing order).

Firstly, I solve it in binary search method with O(NlogN). But after double think, a dynamic programming  solution with O(N) is possible.

Leave a Reply

Your email address will not be published. Required fields are marked *