在Java中搜索堆棧中最大元素的最快方法是什麼？

我有一個問題，我必須搜索堆棧中的最大元素。我已經建立了我自己的堆棧類，並使用以下方法：在Java中搜索堆棧中最大元素的最快方法是什麼？

Node node = top; //created a new node which points to the top of stack 

    int max = node.data; //max contains the value of the top node 

    while(node != null) { 
      if(node.data > max) { 
       max = node.data; 
      } 
      node = node.next; 
    } 

    //Print the value of max.

任何人都可以提出一個更有效的方式來做到這一點？

來源

2017-07-13 artenson.art98

除非你的籌碼是某種排序沒有比O（n）的更快的方法！？你可以使用多線程解決方案，但可能就是這樣。 – xander

維護兩個堆棧：

包括所有節點。
始終將最大節點保留在其頂部，這使得每次都可以輕鬆獲取最大元素。

的代碼是這樣的：

import java.util.Stack; 

public class StackWithMax extends Stack<Integer> { 

Stack<Integer> s2; 

public StackWithMax() { 
    s2 = new Stack<Integer>();  
} 

public void push(int value){ 
    if (value >= max()) { 
     s2.push(value); 
    } 
    super.push(value); 
} 

public Integer pop() { 
    int value = super.pop(); 
    if (value == max()) { 
     s2.pop();   
    } 
    return value; 
} 

public int max() { 
    if (s2.isEmpty()) { 
     return Integer.MIN_VALUE; 
    } else { 
     return s2.peek(); 
    } 
    } 
}

來源

2017-07-13 06:15:39

如果你這樣做，爲什麼不簡單地在棧類中保存一個'int max'而不是另一個棧？ – xander

@Xander如果你只保存一個'max'，那麼當你彈出一個元素時，你必須通過整個堆棧再次找出'max'。 – ajb

@Xander比我們必須通過整個堆棧再次找到最大值。 –

如果你細使用一個額外的空間，我們可以在O做GetMax的（）（1）時間。這個想法是使用基於比較器的PriorityQueue，該比較器返回兩個元素的最大值。您的PriorityQueue將包含基於比較器以排序方式排列的元素。無論何時，當你推入堆棧中的一個元素時，你也可以在PriorityQueue中推入與該元素相對應的最大元素。我們舉一個例子：

假設在你的堆棧中推送元素3.然後在你的priorityQueue pQ中，你會提供3個。此時，3將是堆棧中對應於3的最大元素。

允許在堆疊S中插入5.提供5在pQ中。由於5> 3，pQ中元素的順序將爲5 3. 讓我們在S中推送4。現在pQ將包含以下元素：5 4 3.如果您執行getMax（），您將獲得pQ的頭部，這會花費O（1）次，因爲最大元素始終位於pQ的頂部。

在S.pop（）的情況下，如果以LinkedList的形式存儲pQ，則可以從pQ以及O（1）時間中刪除相應的彈出元素。因此，所有這些操作確實需要O（1）次。

通過相同的邏輯，你也可以在O（1）時間內做popMax（）。只需返回pQ的頭部，並從Stack中刪除相應的節點，這又可以在O（1）的時間內完成。

這裏是兩者的結構如何能：

public class Node{ 
    int data; 
    Node next; 
    Node(int data){ 
     this.data = data; 
     next = null; 
    } 
} 

PriorityQueue<Node> pQ = new PriorityQueue<Node>(); 
Stack<Node> S = new Stack<Node>();

來源

2017-07-13 08:32:22 CodeHunter

在Java中搜索堆棧中最大元素的最快方法是什麼？

回答

相關問題