在Java中計算（不設計！）堆棧的最小值

我想寫一個函數來計算（不是設計）給定堆棧的最小值。我認爲我可以在網上輕鬆找到，但我發現沒有什麼。我發現的所有內容都是如何用getMinimum函數設計堆棧。在Java中計算（不設計！）堆棧的最小值

不同之處在於，當您設計這樣的堆棧時，您將逐步構建堆棧（推送和彈出）並在任何操作後更新最小值。我在想，如果你有一個給定的堆棧，並且你想計算這個堆棧的最小值，那麼你如何處理這個堆棧呢？也許，我沒有很好的理由，或者我問自己錯誤的答案，或者我不太瞭解堆棧的概念，但是讓我感到驚訝的是，在網絡中沒有找到任何答案，甚至在很多搜索...

這裏是我的嘗試：

public static int min(Stack stack){ 
     Stack temp = new Stack(); 
     int result = Integer.MAX_VALUE; 
     while(!stack.isEmpty()) { 
       int value = stack.pop(); 
       temp.push(value); 
       result = (result >= value)? value : result; 
      } 
    //stack is empty now, I have to recuperate it from the temp stack 
      while(!temp.isEmpty()) { 
        stack.push(temp.pop()); 
      } 

      return result; 
     }

在這段代碼中，我用我自己的堆棧和節點實施。但正如你所看到的，代碼非常簡單。我寫這篇文章主要是因爲我問了很多關於這個問題的問題。

特別是，我想問問你請了三個主要問題：

是什麼時候和這個功能的空間複雜度？我認爲這是O（N），是不是？我在計劃中總會遇到一些困難。它通常是O（2 * N）（它等於O（N）），因爲我們運行每個節點的堆棧節點。
我的方法是否合乎邏輯？據我所知，如果你想獲得棧中第k個元素的訪問權限，你必須彈出k-1之前的元素。或者在這裏，我認爲，如果我們只想調整其最小值（如果您想再次操作同一個堆棧），那麼彈出整個堆棧是絕對不合邏輯的。這就是爲什麼我做了第二個while循環來保持堆棧處於原始狀態。
也許，我們可以製作一個堆棧的副本，但是我讀到用java編寫克隆對象並不那麼容易，我想知道這樣的一個小函數是否會消耗很多？

感謝

來源

2016-05-07 salamanka44

另外，如果你不想修改「addToStack」功能，你真的不能讓這個分功能更好，所以是您的解決方案我也會嘗試。我也想說，複雜性是O（n） – Dodekeract

恩，我在我的IDE中嘗試過，它的工作原理。但說實話，這不是真正的計算分鐘（它可以是最大或其他）。它更多的是瞭解堆棧概念背後的概念和效用:) – salamanka44

是的，是的，是的（不要使用克隆，永遠，我懷疑你的攻擊類實現它合理）。這在代碼審查方面確實會更好，但總體思路是正確的。 – Voo

時間和空間確實爲O（n）爲你解釋。
你的方法中有邏輯。但是，您可以以允許您實現peek（int index）的方式實現堆棧 - （例如，如果您的堆棧基於數組），然後不必在插入所有元素時彈出。
您可以在您的Stack實現中保存額外的排序數據結構，這將允許您獲取O（1）中的最小值，但會使用的空間加倍。最後，它總是在空間和時間之間進行權衡。

來源

2016-05-07 18:42:29 aviad

這將是使用遞歸輕鬆了不少：

int min(Stack stack) { 
    if(stack.isEmpty()) 
     return Integer.MAX_VALUE; 

    int temp = stack.pop(); 
    int min = Math.min(temp, min(stack)); 
    stack.push(temp); 

    return min; 
}

來源

2016-05-07 18:44:30

這個解決方案在使用巨大堆棧時不會破壞嗎？難道這不容易導致「太多的遞歸」錯誤？ – Dodekeract

@Dodekeract當然，CS中沒有免費的午餐。 –

在我看來，一個更好的選擇將是利用Vector能力作爲Stack是Vector在Java中

public static int min(Stack<Integer> stack) { 
    Integer[] elements = stack.toArray(new Integer[1]); 
    int min = Integer.MAX_VALUE; 
    for(int i=0;i<elements.length;i++) { 
     if(elements[i] < min) { 
      min=elements[i]; 
     } 
    } 
    return min; 
}

一個子類

這將使您通過自己實施的方法獲得更大的輸入數據性能。

希望這會有所幫助。

來源

2016-05-07 18:46:38 Sanjeev

我正要說同樣的事情...... – selbie

一個更正。我不認爲'[]'運算符被重載。而不是'elements [i]'說，'elements.get（i）' – selbie

它的一個數組和數組只能用'[]'來訪問。請看第一行。 – Sanjeev

Java中的Stack類繼承自Vector。因此，您可以枚舉項目而無需執行任何推送，彈出或複製操作。有了這樣說，這裏是一個O（N）解決方案：

public static int min(Stack stack) { 
    int m = Integer.MAX_VALUE; 
    for (int i = 0; i < stack.size(); i++) { 

     int current = stack.get(i).intValue(); 

     if (current < m) 
     { 
      m = current; 
     } 
    } 
    return m; 
}

來源

2016-05-09 01:47:42 selbie

在Java中計算（不設計！）堆棧的最小值

回答

相關問題