查找堆棧數量最多隻使用PUSH和POP操作

Question

誰能請幫助我的算法對於這個問題（它的一個面試問題）：

給你一個堆棧。設計一個算法，只使用PUSH/POP操作來查找最大數量 。

Answer 1

鑑於在原崗位缺乏約束，你可以彈出了所有的數據和計算運行最大值：

if empty(st) -> raise exception 
m <- pop(st) 
while not empty(st) 
    n <- pop(st) 
    if n > m 
     m <- n 

編輯（用新的限制，原來的堆棧不變，第二個可用的堆棧的新資源）：

if empty(st) -> raise exception 
m <- pop(st) 
push(alt_st, m) 
while not empty(st) 
    n <- pop(st) 
    push(alt_st, n) 
    if n > m 
     m <- n 
while not empty(alt_st): 
    n <- pop(alt_st) 
    push(st, n) 

Answer 2

因爲原來的堆棧不能只讀（Pop，訪問數據的唯一途徑，也改變棧），我們必須考慮到，「日e棧應該不變「的限制意味着我們必須在完成後將其恢復到原始狀態。

我們可以通過使用方法的另一組由雷蒙德赫廷傑建議去做：

int get_max_from_stack(Stack stack) { 
    int M = stack.pop(); 
    Stack aux; 
    aux.push(M); 
    while (!stack.empty()){ 
     int tmp = stack.pop(); 
     aux.push(tmp); 
     M = max(M, tmp); 
    }; 

    while (!aux.empty()) 
     stack.push(aux.pop()); 

    return M; 
}; 

Answer 3

有解決這個問題的方式有兩種，你可以做一個函數get_max這給在堆棧中的最大數量，或者您可以保留一些額外的信息，您可以在O(1)操作中給出堆棧中的最大數量，但代價爲extra space。我會給你後一種解決方案。

您需要做的就是擁有一個extra stack，該堆棧的最大元素位於頂部，用於堆棧的任何配置。

1. 當你按下一個號碼給您原來的堆棧，請執行下列操作爲max_stack，比較max_stack頂部的當前值和推動更大的一個在其上。
2. 當你取出了一些簡單的流行從max_stack
3. 最上面的號碼當你需要找出max值隨便挑棧頂從max_stack。

這樣你就可以獲得O(1)時間內的最大數字，而推動和彈出操作也仍然是O(1)。我可以給你代碼，但沒有什麼內容，因爲它很簡單。例如，如果您在訂單

5 - 2 - 6 - 8 - 1

max_stack推下面的數字將包含

5 - 5 - 6 - 8 - 8

，併爲您pop號碼的當前max將在頂部。

我希望解決方案很明確。