堆棧排序O（N）

Question

我創建一個方法來測試給定的堆棧是否排序。我已經完成了程序的主要任務，但有沒有一種方法可以實現這個算法，而不需要O（N^2）。我想用O（N）得到這個。這樣的解決方案是否存在？如果有的話可以有人指出我的方向正確。

一些規則 - 只能製作一個輔助堆棧。 - 沒有額外的數據結構。 - 如果堆棧爲空或有一個項目，則假定它已被分類。 - 必須在O（N）執行

public static boolean isSorted(Stack s){ 

    boolean sorted = true; 
    Stack backup = new Stack(); 

    int prev, curr; 

    if(s.isEmpty() || s.size() == 1) { 

     sorted = true; 

    } else { 

     while(!s.isEmpty()){ 

      prev = s.pop(); 
      backup.push(prev); 

      curr = s.pop(); 
      backup.push(curr); 

      if(prev > curr && sorted) 
       sorted = false; 

     } 

    } 

    while(!backup.isEmpty()) { 
     s.push(backup.pop()); 
    } 


    return sorted; 

} 

樣品輸入：{20,20,17,11,9,8,3,2}

輸出：

top 2 3 8 9 11 17 20 20 bottom 
| isSorted = true 
| top 2 3 8 9 11 17 20 20 bottom 

在函數結束時。給出的堆棧應該處於其原始狀態。我只是爲O得到這個（N）

Answer 1

你在這裏提出的概念是不爲O（n ），但確實爲O（n） - 堆棧中的每個元素執行一個常數無論N的大小如何。

但是，您應該注意，您有一個錯誤 - 在循環的每次迭代中，您彈出兩個元素並對它們進行比較，因此只有在每個元素對元素進行排序，而不是整個集合（例如，使用值{2,1,500,400}）來嘗試此算法）。此外，請注意，連續的相等值不會中斷排序，因此您應該使用>=而不是>。另一種優化可以快速失敗，一旦你發現堆棧未分類：

public static boolean isSorted(Stack s) { 

    boolean sorted = true; 
    Stack backup = new Stack(); 

    int prev; 
    int curr = Integer.MIN_VALUE; 

    while (!s.isEmpty() && sorted) { 
     prev = curr; 
     curr = s.pop(); 
     backup.push(curr); 
     sorted = (prev <= curr); 
    } 

    while (!backup.isEmpty()) { 
     s.push(backup.pop()); 
    } 

    return sorted; 
}