Berechnen (nicht entwerfen!) Das Minimum eines Stapels in Java

Question

Ich möchte eine Funktion zu berechnen (nicht Design) das Minimum eines gegebenen Stack. Ich dachte, dass ich das leicht im Netz finden kann, aber ich fand nichts darüber. Alles, was ich gefunden habe, ist, wie man einen Stack mit einer getMinimum-Funktion entwirft.

Der Unterschied besteht darin, dass Sie beim Entwerfen eines solchen Stapels Ihren Stapel (Push und Pop) schrittweise aufbauen und den Mindestwert nach jedem Vorgang aktualisieren. Ich dachte, wie wenn Sie einen gegebenen Stapel haben und Sie wollen das Minimum dieses Stapels berechnen, wie können Sie damit umgehen? Vielleicht verstehe ich nicht sehr gut oder ich frage mich die falschen Antworten oder ich verstehe das Konzept des Stacks nicht sehr gut, aber es überrascht mich, im Netz keine Antwort darauf zu finden, auch nicht danach eine Menge Suche ...

Hier mein Versuch ist:

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; 
     } 

In diesem Code verwende ich meine eigene Implementierung für Stapel und Knoten. Aber wie Sie sehen können, ist der Code sehr einfach. Ich habe diesen Beitrag hauptsächlich geschrieben, weil ich mir viele Fragen dazu stelle.

Vor allem möchte ich Ihnen drei Fragen stellen bitte:

• Was ist die Zeit und der Raum Komplexität für diese Funktion? Ich denke, es ist O (N), ist es richtig? Ich habe immer Schwierigkeiten, das in meinem Programm zu berechnen. Es ist normalerweise O (2 * N) (was O (N) entspricht), da wir den Stack-Knoten pro Knoten durchlaufen.
• Ist mein Ansatz logisch oder nicht? Von dem, was ich verstehe, wenn Sie Zugriff auf das k-te Element in einem Stapel haben wollen, müssen Sie das k-1 vorherige Element aufklappen. Oder hier, meiner Meinung nach, ist es absolut nicht logisch, einen ganzen Stapel aufzuspielen, wenn wir nur sein Minimum berechnen wollen (wenn Sie wieder denselben Stapel manipulieren wollen). Deshalb habe ich eine zweite While-Schleife gemacht, um den Stack in seinem ursprünglichen Zustand zu halten.
• Vielleicht können wir eine Kopie des Stapels machen, aber ich habe gelesen, dass das Klonen von Objekten in Java nicht so einfach ist und ich frage mich, ob es für eine kleine Funktion wie diese nicht sehr aufwändig ist?

Dank

Answer 1

1. Zeit und Raum ist in der Tat O (n), wie Sie erklärt.

2. Ihre Methode ist logisch. Sie können Ihren Stack jedoch so implementieren, dass Sie peek (int index) implementieren können (zB wenn Ihr Stack auf einem Array basiert.) Und dann müssen Sie nicht alle Elemente einfügen.

3. Sie können zusätzliche sortierte Datenstruktur in Ihrer Stack-Implementierung speichern, mit der Sie den minimalen Wert in O (1) abrufen können, aber den verwendeten Speicherplatz verdoppeln. am Ende ist es immer ein Kompromiss zwischen Raum und Zeit.

Answer 2

Diese viel einfacher mit Rekursion wäre:

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; 
} 

Answer 3

Meiner Meinung nach, wird eine bessere Option Vector Fähigkeiten zu nutzen sein als Stack eine Unterklasse von Vector in Java

ist

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; 
} 

Dies soll Ihnen eine bessere Leistung für große Eingabedaten gegenüber Ihrer eigenen implementierten Methode bieten.

Hoffe, das hilft.

Answer 4

Die Stack-Klasse in Java erbt von Vector. Sie können also nur die Elemente aufzählen, ohne Push-, Pop- oder Kopiervorgänge ausführen zu müssen. Mit diesem wird gesagt, hier ist eine O (N) Lösung:

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; 
}