python - 转换整数数组并计算总和

Question

假设我们需要转换一个整数数组，然后计算总和。

转换如下:

对于数组中的每个整数，减去第一个等于或小于其值的后续整数。

例如数组:

[6, 1, 3, 4, 6, 2]

变成了

[5, 1, 1, 2, 4, 2]

因为

6 > 1 so 6 - 1 = 5
nothing <= to 1 so 1 remains 1
3 > 2 so 3 - 2 = 1
4 > 2 so 4 - 2 = 2
6 > 2 so 6 - 2 = 4
nothing <= to 2 so 2 remains 2

so we sum [5, 1, 1, 2, 4, 2] = 15

我已经有了下面的答案，但显然有一个更优化的方法。我的答案以二次时间复杂度(嵌套 for 循环)运行，我不知道如何优化它。

prices = [6, 1, 3, 4, 6, 2]
results = []
counter = 0
num_prices = len(prices)
for each_item in prices:
    flag = True
    counter += 1
    for each_num in range(counter, num_prices):
        if each_item >= prices[each_num] and flag == True:
            cost = each_item - prices[each_num]
            results.append(cost)
            flag = False
    if flag == True:
        results.append(each_item)

print(sum(results))

有人能弄清楚如何比二次时间复杂度更快地回答这个问题吗？我很确定这只能使用 1 个 for 循环来完成，但我不知道要使用的数据结构。

编辑:

我可能错了......我刚刚意识到我可以在 flag = False 之后添加一个 break 语句，这将使我免于一些不必要的迭代。我在测验中回答了这个问题，一半的测试用例表示有更优化的方法。他们可能引用了 break 语句，因此也许没有比使用嵌套 for 循环更快的方法了

Answer 1

您可以使用堆栈(使用 Python 列表实现)。该算法是线性的，因为每个元素最多比较两次(一次与下一个元素比较，一次与下一个小于或等于它的数字)。

def adjusted_total(prices):
    stack = []
    total_substract = i = 0
    n = len(prices)
    while i < n:
      if not stack or stack[-1] < prices[i]:
         stack.append(prices[i])
         i += 1
      else:
         stack.pop()
         total_substract += prices[i]

    return sum(prices) - total_substract

print(adjusted_total([6, 1, 3, 4, 6, 2]))

输出:

15