Dlaczego ten minStack działa?

0

Zastanawiam się dlaczego ten kod działa
Przecież jest bez sensu:


package data.structures;

import java.util.EmptyStackException;

class MinStack {
    private class Node {
        long value;
        Node next;

        Node(long value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node top;
    private long minValue = Long.MAX_VALUE;

    public void push(int x) {
        if (top == null) {
            top = new Node(x, null);
            minValue = x;
            return;
        }

        if (x < minValue) {
            top = new Node(2L*x - minValue, top);
            minValue = x;
        } else {
            top = new Node(x, top);
        }
    }

    public int pop() {
        if (top != null) {
            long prevTopVal = top.value;
            top = top.next;

            if (prevTopVal < minValue) {
                long temp = minValue;
                minValue = 2*minValue - prevTopVal;

                return (int)temp;
            } else {
                return (int)prevTopVal;
            }
        }

        throw new EmptyStackException();
    }

    public int getTop() {
        if (top != null)
            return (int)Math.max(top.value, minValue);

        throw new EmptyStackException();
    }

    public int getMin() {
        if (top != null)
            return (int)minValue;

        throw new EmptyStackException();
    }

    public boolean isEmpty() {
        return top == null;
    }
}

Main:

        MinStack minStack = new MinStack();
        minStack.push(-5);
        minStack.push(13);
        minStack.push(-71);
        minStack.push(0);
        minStack.push(33);

        System.out.println("MinStack tests:");
        System.out.println("Pop: " + minStack.pop());   //33
        System.out.println("GetTop: " + minStack.getTop());   //0
        System.out.println("GetMin: " + minStack.getMin());   //-71
        System.out.println("Pop: " + minStack.pop());      //0
        System.out.println("GetTop: " + minStack.getTop());    //-71
        System.out.println("GetMin: " + minStack.getMin());    //-71
        System.out.println("Pop: " + minStack.pop());         //-71
        System.out.println("GetTop: " + minStack.getTop());   //13
        System.out.println("GetMin: " + minStack.getMin());   //-5
        System.out.println();

CZEMU TEN GÓWNIANY EDYTOR DODAJE SAM WCIĘCIA????

1

Ciekawa konstrukcja :)

Gdy zapisujesz w node:

minStack.push(-5);
minStack.push(13);
minStack.push(-71);
minStack.push(0);
minStack.push(33);

to tak naprawdę zapisujesz:

33
0
-137 // a nie -71
13
-5

Reguła jest taka że jeżeli pojawi się większa ujemna wartość to do node zapisujesz 2 * obecna wartość - (poprzednie minimum). Dzięki czemu zapamiętujesz jakie poprzednie minimum było.

2 * -71 - (-5) = -137

Gdy przychodzi do operacji pop to możesz ponownie obliczyć jakie było poprzednie minimum bo w zmiennej minValue masz zapamiętaną ostatnią minimalną wartość. Więc odwracasz równanie:

2*(-71) - (-137) = -5 

-5 czyli poprzednie minimum.

0

A jak ma dzialać, MinStack?

1 użytkowników online, w tym zalogowanych: 0, gości: 1