stack - 在 O(1) 中实现堆栈(push、pop 和 findmin)

Question

我已经看到这个问题的两个堆栈实现，但我真的很困惑如何获得 O(1) 操作。考虑以下示例:

S1[3542761986759]
S2[3332221111111]

这里的思路/算法是

1. 将元素E推送到S1上
2. 检查 S2 的顶部是否 >= E，如果为真，则在 S2 上插入 E

但是当调用 getMin 时，我们返回了 S2 的顶部，但是由于 S2 包含重复的当前最小元素，这使得 S2 处于奇怪的状态，因此解决方案是在 S2 中搜索下一个最小元素并返回它。这是 O(n)。

任何人都可以帮助我理解解决方案吗？

Answer 1

使用链表存储当前最小值。当您添加一个新数字时，它会查看前一个最小值，如果当前值较低，则将当前最小值更改为当前值。

例如...假设您有数据:3、6、4、2、7、1。那么这就是列表的样子

值|分钟

3|3 -> 6|3 -> 4|3 -> 2|2 -> 7|2 -> 1|1

这将在您推送/弹出项目时跟踪分钟数。当然，您需要有一个根节点和一个指定为“页脚”的节点，以便您可以在 O(1) 中访问结尾。

或者您可以使用它向后退，将内容添加到前面并在每次插入时更改根节点……这也可以。它会是这样的:

1|1 -> 7|2 -> 2|2 -> 4|3 -> 6|3 -> 3|3

那么你就不需要“页脚”节点了。

当值被推送时，这两个都会跟踪当前的最小值。这样当实际的最小值被推送时，它就会知道 O(1) 中的第二个最小值是多少。