如何提高计算最少步数的算法性能速度？

Question

我参加了 codefights 并让任务找到从输入中获得严格递增序列所需的最少移动次数。作为输入，有整数数组，根据规则，我可以每次移动将数组中的一个元素恰好增加一个。

inputArray: [1, 1, 1]
Expected Output:3

inputArray: [-1000, 0, -2, 0]
Expected Output:5

inputArray: [2, 1, 10, 1]
Expected Output:12

inputArray: [2, 3, 3, 5, 5, 5, 4, 12, 12, 10, 15]
Expected Output:13

还有输入输出的条件：

[time limit] 4000ms (py3)
[input] array.integer inputArray
3 ≤ inputArray.length ≤ 105,
-105 ≤ inputArray[i] ≤ 105
[output] integer

我想出了以下解决方案：

def arrayChange(inputArray):
k=0
for i in range(len(inputArray)-1):
    if (inputArray[i]<inputArray[i+1]) == False:
        while inputArray[i+1]<=inputArray[i]:
            inputArray[i+1] = inputArray[i+1] + 1
            k +=1
return k

然而，显然对于一些我无法观察到的测试，我的算法性能超出了时间限制：

6/8 Execution time limit exceeded on test 7: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input. Sample tests: 4/4 Hidden tests: 2/4

如何改进我的算法以提高性能速度？

Answer 1

现在你一次增加1。目前你有这个代码片段：

inputArray[i+1] = inputArray[i+1] + 1

与其每次递增 1，不如一次将所有数字相加？例如，如果您有列表 [1, 3, 0]，则将 4 添加到最后一个元素是有意义的。这样做比加 1 4 次要快得多。

Answer 2

@fileyfood500 给了我一个非常有用的提示，这是我有效的解决方案：

deltX=0
for i in range(len(a)-1):
    if (a[i]<a[i+1]) == False:
        deltX1 = abs(a[i+1]-a[i])+1
        a[i+1] = a[i+1] + deltX1
        deltX += deltX1
print(deltX)

现在我根本不需要 while 循环，因为我增加了项目，应该一步增加必要的数量。

Answer 3

def arrayChange(inputArray):
    count = 0
    for i in range(1,len(inputArray)):
        while inputArray[i] <= inputArray[i-1]:
            c = inputArray[i]
            inputArray[i]= inputArray[i-1]+1
            count += inputArray[i] - c 
    return count

这样直接递增，时间会少
然后只需从先前的值中减去新值即可得到它递增的次数。

如何提高计算最少步数的算法性能速度？

How to increase speed of algorithm performance for calculation minimal number of moves?

algorithm

performance

loops

cycle

python-3.x