在 O(1) 中实现堆栈（push、pop 和 findmin）

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

S1[3542761986759]
S2[3332221111111]

这里的想法/算法是

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

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

谁能帮我理解解决方案吗？

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

例如...假设您有数据：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) 中的第二个最小值是多少。