是否有算法在常量時間內返回堆棧中第二大元素？

Question

我知道如何使用存儲最大值的輔助堆棧爲堆棧中的最大元素執行此操作。想知道這是否可以延長，以在恆定時間內同時返回最大值和最小值。

Answer 1

取而代之的推動最大的元素輔助堆棧上，你把（最大，second_largest）對。或者你可以將它們推到兩個平行的堆棧上。

僞代碼：

int largest = second_largest = MIN_INT; 

push(int x) 
{ 
    stack1.push(x); 
    stack2.push(largest); 
    stack3.push(second_largest); 

    if (x >= largest) 
    { 
     second_largest = largest; 
     largest = x; 
    } 
    else if (x > second_largest) 
    { 
     second_largest = x; 
    } 
} 

int pop() 
{ 
    second_largest = stack3.pop(); 
    largest = stack2.pop(); 
    return stack1.pop(); 
} 

的圖案是一個撤消堆棧。每當push()對您正在跟蹤的內容進行更改時，那麼當您獲得pop()時，您將保存足夠的信息到撤銷這些更改。

Answer 2

您可以創建第二個最大輔助堆棧。這裏是插入一些數字後例如最低和第二最低輔助書庫的想法：

Actual Stack 
16 <--- top  
15 
29 
19 
18 
Auxiliary Stack 
15 <---- top 
15 
18 
18 
18 
Second Auxiliary Stack 
18 <---- top 
18 
N/A 
N/A 
N/A 

恐怕有在輔助棧的情況下，用O（1）的時間複雜度越來越第二最大沒有其他解決辦法。

編輯 - explenation

putting i: 
- put i to main stack 
- if i is smaller than top of 1st auxiliary stack, put it there, if it is not 
    put the same number. 
- if top of 1st auxiliary stack changed, put previous 1st auxiliary top to 2nd 
    auxiliary stack. If it is not just put the same number as it was to the top. 

popping is just popping from each stack.