在O（1）中插入，删除，最大值

有人可以告诉我O（1）中哪个数据结构支持插入/删除/最大操作吗？

这是一个经典的面试问题，通常如下所示：

设计一个类似堆栈的数据结构，该结构在O（1）时间内执行推，弹出和最小（或最大）操作。没有空间限制。

答案是，您使用两个堆栈：主堆栈和最小（或最大）堆栈。

因此，例如，在将1,2,3,4,5推入堆栈后，您的堆栈将如下所示：

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

但是，如果您要推入5,4,3,2,1，则堆栈如下所示：

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

对于5,2,4,3,1您将拥有：

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

等等。

您还可以通过仅在最小元素更改时才推送到最小堆栈来节省一些空间，前提是已知这些项目是不同的。