algorithm - 插入、删除、最大值 O(1)

Question

谁能告诉我哪种数据结构支持 O(1) 的插入/删除/最大值操作？

Answer 1

这是一道经典的面试题，通常是这样呈现的:

Devise a stack-like data structure that does push, pop and min (or max) operations in O(1) time. There are no space constraints.

答案是，您使用两个堆栈:主堆栈和最小(或最大)堆栈。

例如，将 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 |
+---+  +---+

等等。

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