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).
1 2 3 4 5 6 7 | Input: [5, 4, 3, 2, 8] Output: 3 Explanation: after the adjustment, the hills COULD be: 2, 3, 4, 5, 8 There may exist many more accepting final status. We only consider its feasibility. |
Firstly, I solve it in binary search method with O(NlogN). But after double think, a dynamic programming solution with O(N) is possible.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #---------------------------------------------------------------- # Author: Sheng Yu codesays.com # Written: 09/07/2014 # Last updated: 09/07/2014 # # Filename: hill.py # Python Used: 2.7 #----------------------------------------------------------------- import random def _tryHill_bs(v, h): ''' Every hill in v can increase/decrease at most h. Check whether we can get a strictly increasing result, after adjusting the heights. ''' preHeight = v[0] - h for height in v[1:]: if height + h <= preHeight: return False else: preHeight = max(preHeight + 1, height - h) return True def hill_bs(v): ''' Use binary search algorithm to find the minimum change range h, which could adjust the hills to a strictly increasing result. ''' begin = 0 end = max(max(v) - min(v), len(v)) while begin <= end: middle = (begin + end) // 2 if _tryHill_bs(v, middle): end = middle -1 else: begin = middle + 1 return end + 1 def hill_dp(v): ''' Use dynamic programming to find the minimum change range h. ''' result = 0 preHeight = v[0] for height in v[1:]: if height + result <= preHeight: oldResult = result # We need to increase the h, so that current hill will be higher # than the previous one after adjustment. result += (preHeight - height - result) // 2 + 1 # Virtually, we decrease all previous hills by result - oldResult preHeight -= (result - oldResult) preHeight = max(preHeight + 1, height - result) return result def main(): ''' Test stub. Use randomly generated array to test. ''' TEST_CASES = 1000 while TEST_CASES > 0: test = random.sample(xrange(1000000), random.randint(1,10000)) res1 = hill_bs(test) res2 = hill_dp(test) if res1 == res2: print "Test case #" + str(TEST_CASES) + ": PASS." else: print "Test case #" + str(TEST_CASES) + ": FAIL - " + " ".join([str(i) for i in test]); return TEST_CASES -= 1 return if __name__ == "__main__": main() |