在 O(1) 中插入、删除、最大值 [英] insert, delete, max in O(1)

问题描述

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

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

推荐答案

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

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.

这篇关于在 O(1) 中插入、删除、最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！