在O(1)中插入,删除,最大

Question

有人能告诉我哪个数据结构支持O(1)中的插入/删除/最大操作？

Answer 1

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

设计类似堆栈的数据结构,在O(1)时间内执行push,pop和min(或max)操作.没有空间限制.

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

因此,例如,在将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 |
+---+  +---+

等等.

您还可以通过仅在最小元素更改时推送到最小堆栈来节省一些空间,如果已知项目是不同的.

Answer 2

以下解决方案使用O(1)额外内存和O(1)时间进行最大,推送和弹出操作.保持变量max,它将跟踪任何特定时间的当前最大元素.让我们利用这样一个事实:当更新max时,堆栈中的所有元素应该小于新的max元素.当发生推送操作并且新元素(newElement)大于当前最大值时,我们将推送堆栈中的max + newElement并更新max = newElement.

当我们进行弹出操作并且我们发现当前弹出元素大于当前最大值时,我们知道这是我们更新堆栈以保持max + elem的位置.因此,要返回的实际元素是max和max = poppedElem - max.

例如.如果我们正在推动1,2,3,4,5,那么堆栈和最大变量将如下所示:

MAIN       Value of MAX
+---+      +---+
| 9 |      max = | 5 |
| 7 |      max = | 4 |
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

现在让我们说我们弹出一个元素,我们将基本上弹出,max元素(因为top> max)并将max元素更新为(top-max)

MAIN       Value of MAX
+---+      +---+
| 7 |      max = | 4 | = (9-5)
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

现在让我们说我们正在推动数字5,4,3,2,1,堆栈看起来像:

MAIN       Value of MAX
+---+      +---+
| 1 |      max = | 5 |
| 2 |      max = | 5 |
| 3 |      max = | 5 |
| 4 |      max = | 5 |
| 5 |      max = | 5 |
+---+      +---+

当我们弹出时,堆栈的顶部会弹出,因为顶部<max,并且max保持不变.

以下是每个操作的伪代码,以便更好地了解.

Elem max;
void Push(Elem x){
    if x < max :
        push(x);
    else{
        push(x+max);
        max = x;
    }
}
Elem Pop(){
    Elem p = pop();
    if |p| < |max|:
        return p;
    else{
        max = p - max;
        return max;
    }
}
Elem Max(){
    return max;
}

push和pop是正常的堆栈操作.希望这可以帮助.

Answer 3

@ KennyTM的评论指出了一个重要的缺失细节 - 插入位置,并从中删除.所以我假设你总是希望只从堆栈的一端插入和删除.

插入(推送)和删除(弹出)是O(1).

要在O(1)中获取Max,请使用额外的堆栈来记录与主堆栈对应的当前最大值.