问表示移除序列的序列生成算法

EN

是的，可以使用单个堆栈来完成，我将描述解决方案，并在稍后简要解释其工作原因。

假设数组是A = [0, 9, 8, 7, 9, 8, 7, 5]，Ans = [] be the array of corresponding answer。我们还维护一个最初为空的堆栈S。堆栈将存储对{A[i], Ans[i]}，我们将尝试保存堆栈，以便始终严格增加A[i]上的，如下所示：

1. 将{A[0], 0}推送到S
2. 通过数组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

让我们根据您的示例进行演示：

1. A = [0, 9, 8, 7, 9, 8, 7, 5], Ans = [0, -1, -1, -1, -1, -1, -1, -1], S = [{0,0}]
2. A[1] = 9 and S.top()已经小于9，不会弹出任何元素。Ans[1] = round_to_wait + 1 = 0 + 1 = 1，将{9, 1}推入S A = [0, 9, 8, 7, 9, 8, 7, 5], Ans = [0, 1, -1, -1, -1, -1, -1, -1], S = [{0,0}, {9,1}]
3. 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}]
4. 类似地，S = [{0,0}, {7,3}]
5. 类似地，S = [{0,0}, {7,3}, {9,1}]
6. 类似地，S = [{0,0}, {7,3}, {8,2}]
7. 类似地，S = [{0,0}, {7,4}]
8. 类似地，S = [{0,0}, {5,5}]

就这样，你在一个循环中得到答案。由于每个元素最多只被推一次并弹出一次，其复杂性仍然是O(N)。

为什么它起作用是因为，假设A[i]是第一个没有与S形成严格递增序列的元素，这意味着什么？

这意味着，在某种程度上，S S_top中的顶级元素将“阻止”我们删除A[i]。只有当A[i]被删除时，我们才有机会(但不是充分条件)删除S_top，这意味着它至少与Ans[S_top] + 1一样快，并且我们在所有这些元素中取最大值。

特例是，根本没有比A[i]更小的元素，这意味着S最终将是空的，在这种情况下是Ans[i] = 0。

(PS:几年前，我想我在一些在线法官上有一些关于这个问题的记忆，如果这是来源，你能把它发出来吗，这样我就可以去提交来验证解决方案了吗？)