谁能告诉我哪个数据结构支持插入/删除/ O型最大工作（1）？

Can someone tell me which data structure supports insert/delete/maximum operation in O(1)?

推荐答案

这是一个经典的面试问题，通常是$ psented像这名P $：

This is a classical interview question, and is usually presented like this:

设计一个类栈的数据结构，做推，流行音乐和最小（或最大）操作在O（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.

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

The answer is, you use two stacks: the main stack, and a min (or max) stack.

因此​​，例如，1,2,3,4,5推入堆栈后，你的筹码应该是这样的：

So for example, after pushing 1,2,3,4,5 onto the stack, your stacks would look like this:

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

不过，如果你推5,4,3,2,1，堆是这样的：

However, if you were to push 5,4,3,2,1, the stacks would look like this:

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

有关5,2,4,3,1你会：

For 5,2,4,3,1 you would have:

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

等等。

您也可以通过推到最小栈仅当最小元素的变化，当且仅当物品是已知的不同的节省一些空间。

You can also save some space by pushing to the min stack only when the minimum element changes, iff the items are known to be distinct.