用右边最近的较大整数替换数组中整数的算法
Algorithm to replace integers in array by the nearest bigger integer on their right
你是如何在 O(n) 时间内解决这个问题的？
给定一个未排序的整数数组，设计算法来转换数组，使整数被右边最近的较大整数替换。如果右边没有更大的整数，则整数保持不变。例如，下面的整数数组
2 1 4 5 3 6 7 9 4 8
应该变成
4 4 5 6 6 7 9 9 8 8
初始化整数栈
从左到右
当元素较小时从栈中弹出，并替换为当前
将元素的id添加到堆栈
请注意，堆栈将严格递减。并且每个元素最多 popped/added 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)
你是如何在 O(n) 时间内解决这个问题的？
给定一个未排序的整数数组，设计算法来转换数组，使整数被右边最近的较大整数替换。如果右边没有更大的整数，则整数保持不变。例如，下面的整数数组
2 1 4 5 3 6 7 9 4 8
应该变成
4 4 5 6 6 7 9 9 8 8
初始化整数栈
从左到右
当元素较小时从栈中弹出，并替换为当前
将元素的id添加到堆栈
请注意，堆栈将严格递减。并且每个元素最多 popped/added 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)