給出一個數列，每一次操作可以將其中一個數換成兩個數，兩數之和和原數一樣，問最少幾次操作可以將數列變成單調不減，貪心思想，最后一個數作為初始值，如果前一個數比他大，盡量分裂成更大更相等的幾個數，不斷和前一個數比直到數列頭
1 #2366
2 #Runtime: 432 ms (Beats 100%) Sorry, there are not enough accepted submissions to show data
3 #Memory: 25.8 MB (Beats 100%) Sorry, there are not enough accepted submissions to show data
4
5 class Solution(object):
6 def minimumReplacement(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 pre = nums[-1]
12 ans = 0
13 for i in range(len(nums) - 1, -1, -1):
14 d = nums[i] // pre
15 if nums[i] % pre != 0:
16 d += 1
17 ans += d - 1
18 pre = nums[i] // d
19 return ans