wake-up-neo.com

Stack mit Find-Min/Find-Max effizienter als O (n)?

Ich bin daran interessiert, eine Java-Datenstruktur ähnlich einem Stack zu erstellen, die die folgenden Operationen so effizient wie möglich unterstützt:

  • Push, wodurch ein neues Element auf dem Stapel hinzugefügt wird.
  • Pop, der das oberste Element des Stapels entfernt,
  • Find-Max, das das größte Element des Stapels zurückgibt (aber nicht entfernt), und
  • Find-Min, das das kleinste Element des Stapels zurückgibt (aber nicht entfernt), und

Was wäre die schnellste Implementierung dieser Datenstruktur? Wie kann ich es in Java schreiben?

48
Techkriti

Dies ist eine klassische Frage der Datenstruktur. Die Intuition hinter dem Problem ist wie folgt - die einzige Möglichkeit, dass sich Maximum und Minimum ändern können, ist, wenn Sie einen neuen Wert auf den Stapel legen oder einen neuen Wert aus dem Stapel ziehen. Angenommen, Sie nehmen auf jeder Ebene des Stapels die Maximal- und Mindestwerte an oder unter diesem Punkt im Stapel fest. Wenn Sie dann ein neues Element auf den Stapel schieben, können Sie den maximalen und den minimalen Wert an einer beliebigen Stelle im Stapel leicht (in der Zeit O(1)) berechnen, indem Sie das gerade geschobene neue Element mit dem aktuellen Maximum und vergleichen Minimum. Wenn Sie ein Element entfernen, legen Sie das Element im Stapel einen Schritt unter dem oberen Rand frei, der bereits die maximalen und minimalen Werte des restlichen Stapels enthält.

Angenommen, wir haben einen Stapel und fügen die Werte 2, 7, 1, 8, 3 und 9 in dieser Reihenfolge hinzu. Wir fangen mit 2 an und drücken 2 auf unseren Stack. Da 2 nun auch der größte und kleinste Wert im Stack ist, zeichnen wir dies auf:

 2  (max 2, min 2)

Nun lassen Sie uns 7 drücken. Da 7 größer als 2 ist (das aktuelle Maximum), erhalten wir folgendes:

 7  (max 7, min 2)
 2  (max 2, min 2)

Beachten Sie, dass wir jetzt die maximalen und minimalen Werte des Stapels ablesen können, indem wir oben auf den Stapel schauen und sehen, dass 7 das Maximum und 2 das Minimum ist. Wenn wir jetzt 1 drücken, bekommen wir

 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

Hier wissen wir, dass 1 das Minimum ist, da wir 1 mit dem zwischengespeicherten Mindestwert vergleichen können, der auf dem Stack gespeichert ist (2). Stellen Sie als Übung sicher, dass Sie verstehen, warum wir nach dem Hinzufügen von 8, 3 und 9 Folgendes erhalten:

 9  (max 9, min 1)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

Wenn Sie nun das Maximum und das Min. Abfragen möchten, können Sie dies in O(1) tun, indem Sie einfach die gespeicherten Max und Min auf dem Stack ablesen (9 bzw. 1).

Nehmen wir an, dass wir das oberste Element entfernen. Dies ergibt 9 und modifiziert den Stapel 

 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

Und jetzt stellen Sie fest, dass das Maximum dieser Elemente 8 ist, genau die richtige Antwort! Wenn wir dann 0 drücken, würden wir folgendes bekommen:

 0  (max 8, min 0)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

Wie Sie sehen können, werden Max und Min korrekt berechnet.

Insgesamt führt dies zu einer Implementierung des Stapels mit O(1) Push, Pop, Find-Max und Find-Min. Dies ist so asymptotisch, wie es nur geht. Ich lasse die Implementierung als Übung. :-) Möglicherweise möchten Sie jedoch die Implementierung des Stacks mit einer der standardmäßigen Stack-Implementierungstechniken in Betracht ziehen, z. B. mit einem dynamischen Array oder Linked List von Objekten, von denen jedes gilt das Stack-Element, min und max. Sie können dies leicht tun, indem Sie ArrayList oder LinkedList verwenden. Alternativ können Sie die bereitgestellte Java-Klasse Stack verwenden. IIRC hat jedoch aufgrund der Synchronisierung einen gewissen Overhead, der für diese Anwendung möglicherweise nicht erforderlich ist.

Wenn Sie einen Stapel mit diesen Eigenschaften erstellt haben, können Sie ihn als Baustein verwenden, um eine Warteschlange mit denselben Eigenschaften und Zeitgarantien zu erstellen. Sie können es auch in einer komplexeren Konstruktion verwenden, um eine doppelendige Warteschlange mit diesen Eigenschaften zu erstellen.

Hoffe das hilft!

EDIT: Wenn Sie neugierig sind, habe ich C++ - Implementierungen von EIN MIN-STACK und eine der oben genannten MIN-QUEUE auf meiner persönliche Website Hoffentlich zeigt dies, wie das in der Praxis aussehen könnte!

110
templatetypedef

Die Antwort ist zwar richtig, aber wir können es besser machen. Wenn der Stapel viele Elemente enthält, verschwenden wir viel Platz. Wir können diesen nutzlosen Speicherplatz jedoch wie folgt speichern:

Statt mit jedem Element einen minimalen (oder maximalen) Wert zu speichern, können wir zwei Stapel verwenden. Da die Änderung des minimalen (oder maximalen) Werts nicht so häufig erfolgt, verschieben wir den min (oder max) Wert nur dann in den entsprechenden Stapel, wenn der neue Wert <= (oder >=) auf den aktuellen min (oder max) Wert lautet.

Hier ist die Implementierung in Java:

public class StackWithMinMax extends Stack<Integer> {

    private Stack<Integer> minStack;
    private Stack<Integer> maxStack;

    public StackWithMinMax () {
        minStack = new Stack<Integer>();    
        maxStack = new Stack<Integer>();    
    }

    public void Push(int value){
        if (value <= min()) { // Note the '=' sign here
            minStack.Push(value);
        }

        if (value >= max()) {
            maxStack.Push(value);
        }

        super.Push(value);
    }

    public Integer pop() {
        int value = super.pop();

        if (value == min()) {
            minStack.pop();         
        }

        if (value == max()) {
            maxStack.pop();         
        }

        return value;
    }

    public int min() {
        if (minStack.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

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

Beachten Sie, dass wir mit diesem Ansatz sehr wenige Elemente in minStack & maxStack haben würden, um Platz zu sparen. z.B.

Stack : MinStack : MaxStack

7         7         7
4         4         7
5         1         8 (TOP)
6         1 (TOP)         
7
8                 
1                  
1                  
7
2
4
2 (TOP)     
30
Vasu

Möglicherweise ist es zu spät, um zu antworten, aber nur der Aufzeichnung halber. Hier ist der Java-Code.

import Java.util.ArrayList;
import Java.util.List;

public class MinStack {
    List<Node> items;

    public void Push(int num) {
        if (items == null) {
            items = new ArrayList<Node>();
        }
        Node node = new Node(num);
        if (items.size() > 0) {
            node.min = Math.min(items.get(items.size() - 1).min, num);
            node.max = Math.max(items.get(items.size() - 1).max, num);

        } else {
            node.min = num;
            node.max = num;
        }
        items.add(node);
        printStack();
    }

    public Node pop() {
        Node popThis = null;
        if (items != null && items.size() > 0) {
            popThis = this.items.get(items.size() - 1);
            items.remove(items.size() - 1);         
        }
        printStack();
        return popThis;
    }

    public int getMin() {
        if (items != null && items.size() > 0) {
            int min = this.items.get(items.size() - 1).min;
            System.out.println("Minimum Element > " + min);
            return min;
        }
        return -1;
    }

    public int getMax() {
        if (items != null && items.size() > 0) {
            int max = this.items.get(items.size() - 1).max;
            System.out.println("Maximum Element > " + max);
            return max;
        }
        return -1;
    }

    public void printStack() {
        int i = 0;
        for (Node n : items) {
            System.out.print(n.data + " > ");
            if (i == items.size() - 1) {
                System.out.print(" | Min = " + n.min + " |");
                System.out.print(" | Max = " + n.max + " |");

            }
            i++;
        }
        System.out.println();
    }

    public static void main(String args[]) {
        MinStack stack = new MinStack();
        stack.Push(10);

        stack.Push(13);
        stack.Push(19);
        stack.Push(3);
        stack.Push(2);
        stack.Push(2);
        stack.printStack();
        stack.pop();
        //stack.getMin();
        stack.printStack();

    }
}

Stapelklasse:

class Node {

        int data;
        int min;
        int max;

        public Node(int data) {
            super();
            this.data = data;
        }

        public Node() {
            super();
        }
    }
2
Sanjay Kumar

Verknüpfte Liste verwenden:

public class MaxMinStack {
    MaxMinLLNode headMin = null;
    MaxMinLLNode headMax = null;
    MaxMinLLNode tailMin = null;
    MaxMinLLNode tailMax = null;

    public void Push(int data) {
        MaxMinLLNode node = new MaxMinLLNode(data, null);
        if (headMin == null) {
            headMin = node;
            tailMin = node;
        } else {
            if (data < headMin.data) {
                tailMin = headMin;
                headMin = node;
                node.nextNodeReference = tailMin;
            }
        }

        if (headMax == null) {
            headMax = node;
            tailMax = node;
        } else {
            if (data > headMax.data) {
                tailMax = headMax;
                headMax = node;
                node.nextNodeReference = tailMax;
            }
        }

    }

    public void pop() {
        System.out.println("Max Element:" + " " + String.valueOf(headMax.data));
        System.out.println("Min Element:" + " " + String.valueOf(headMin.data));
    }

    public void traverse() {
        MaxMinLLNode ptrMin = headMin;
        MaxMinLLNode ptrMax = headMax;
        System.out.println("Min");
        while (ptrMin != null) {
            System.out.println(ptrMin.data);
            ptrMin = ptrMin.nextNodeReference;
        }

        System.out.println("Max");
        while (ptrMax != null) {
            System.out.println(ptrMax.data);
            ptrMax = ptrMax.nextNodeReference;
        }

    }

    public static void main(String[] args) {
        MaxMinStack m = new MaxMinStack();
         m.Push(7);
         m.Push(4);
         m.Push(5);
         m.Push(6);
         m.Push(7);
         m.Push(8);
         m.Push(1);
         m.Push(1);
         m.Push(7);
         m.Push(2);
         m.Push(4);
         m.Push(2);
         m.traverse();
         m.pop();
    }

}

class MaxMinLLNode {
    int data;
    MaxMinLLNode nextNodeReference;

    MaxMinLLNode(int data, MaxMinLLNode node) {
        this.data = data;
        this.nextNodeReference = node;
    }
}
0
Nikita Gupta