给定一个有限的数字序列，在每一轮中，左邻小于其自身的任何数字都将被删除。此删除操作将继续，直到无法删除任何内容。删除的每个数字都将标记为已删除的整数，如果从未删除，则标记为0。
例如，考虑序列
0 9 8 7 9 8 7 5
在第一轮之后，
0 8 7 8 7 5
在连续四轮之后，
0 7 7 5个
0 7 5个
0 5个
0个
因此，数字对应的标签是
0 1 2 3 1 2 4 5
当N是所提供序列的长度时，如何使用堆栈或队列在O（N）时间内生成标签序列或者我可以知道在O（n）时间内的最大删除次数吗？
最佳答案
是的，它可以使用一个堆栈来完成，我将描述解决方案，并在稍后简要解释其工作原理。
假设数组是A = [0, 9, 8, 7, 9, 8, 7, 5]，Ans = [] be the array of corresponding answer。我们还保持最初的空堆栈S。堆栈将存储对{A[i], Ans[i]}，我们将尝试保留堆栈，以便它始终严格地在A[i]上增加，如下所示：
按{A[0], 0}到S
循环数组A。对于迭代的一个实例，让A[i]成为当前的数字（Ans[i]还不知道）：
2a.初始化变量round_to_wait = 0，继续弹出堆栈S直到顶部元素小于A[i]，将rount_to_wait设为最大Ans[x]
2b.如果S为空，则设置Ans[i] = 0，否则设置Ans[i] = round_to_wait + 1
2c.按{A[i], Ans[i]}至S
让我们根据您的示例进行演示：A = [0, 9, 8, 7, 9, 8, 7, 5], Ans = [0, -1, -1, -1, -1, -1, -1, -1], S = [{0,0}]A[1] = 9 and S.top()已经小于9，没有元素被弹出Ans[1] = round_to_wait + 1 = 0 + 1 = 1，将{9, 1}推入SA = [0, 9, 8, 7, 9, 8, 7, 5], Ans = [0, 1, -1, -1, -1, -1, -1, -1], S = [{0,0}, {9,1}]A[2] = 8然后我们弹出元素，直到{0,0}离开。在整个爆裂过程中是最大的。rount_to_wait = 1，将Ans[2] = round_to_wait + 1 = 1 + 1 = 2推入{8, 2}S
同样地，A = [0, 9, 8, 7, 9, 8, 7, 5], Ans = [0, 1, 2, -1, -1, -1, -1, -1], S = [{0,0}, {8,2}]
同样地，S = [{0,0}, {7,3}]
同样地，S = [{0,0}, {7,3}, {9,1}]
同样地，S = [{0,0}, {7,3}, {8,2}]
同样地，S = [{0,0}, {7,4}]
就这样，答案就在一个循环中。当每一个元素最多被推和弹出一次时，复杂性仍然是S = [{0,0}, {5,5}]
它之所以起作用是因为，让O(N)成为第一个不与A[i]形成严格递增序列的元素，这意味着什么？
这意味着，在某个时刻，SS中的顶部元素将“阻止”我们删除S_top只有当“CC”被删除时，我们才有机会（没有足够的条件）删除A[i]，这意味着它至少是A[i]，我们在所有这些元素中取最大值。
特殊情况是，根本没有小于S_top的元素，这意味着Ans[S_top] + 1最终将是空的，在这种情况下A[i]
（附：几年前我在网上的一些法官那里想我对这个问题有一些记忆，如果是这个来源的话，你可以把它发出去，这样我就可以去提交验证解决方案了吗？）