插入、删除、最大值 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 |
+---+  +---+

等等。

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