arrays - 用右边最近的较大整数替换数组中整数的算法

Question

如何在 O(n) 时间内解决这个问题？

给定一个未排序的整数数组，设计算法来转换数组，使整数被右边最近的较大整数替换。如果右边没有更大的整数，则整数保持不变。例如下面的整数数组

2 1 4 5 3 6 7 9 4 8

应该变成

4 4 5 6 6 7 9 9 8 8

Answer 1

• 初始化整数栈

• 从左到右。

• 当元素较小时从栈中弹出，并替换为当前元素

• 将元素的id添加到栈中

请注意，堆栈将严格递减。并且每个元素最多弹出/添加 1 次。因此 O(N)

Python 示例代码:

l = [2, 1, 4, 5, 3, 6, 7, 9, 4, 8]
s = [0]
for i in range(1, len(l)):
    while s and l[i] > l[s[-1]]:
        l[s.pop()] = l[i]
    s.append(i)