【LeetCode】Min Stock解題報告

【タイトル】
Design a stack that supports push,pop,top,and retrieving the minimum element in constant time.
push(x)--Push element x onto stack.pop()--Removes the element on top of the stack.top()--Get the top element.getMin()--Retrieve the minimum element in the stack.【Java内蔵のStockで実現】
来た:https://oj.leetcode.com/discuss/15659/simple-java-solution-using-two-build-in-stacks?state=edit-15691&show=15699{q 15699

class MinStack {
    // stack: store the stack numbers
    private Stack<Integer> stack = new Stack<Integer>();
    // minStack: store the current min values
    private Stack<Integer> minStack = new Stack<Integer>();

    public void push(int x) {
        // store current min value into minStack
        if (minStack.isEmpty() || x <= minStack.peek())
            minStack.push(x);
        stack.push(x);
    }

    public void pop() {
        // use equals to compare the value of two object, if equal, pop both of them
        if (stack.peek().equals(minStack.peek()))
            minStack.pop();
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

【分析】
この問題のキーポイントは、minStockのデザインです.Push()pop()top()これらの操作はJava内蔵のStockが全部あります.これは言うまでもありません.
最初は二つの配列を作りたいと思っていましたが、それぞれの要素の前の方が大きいのと後の方が小さいのとを記録しています.複雑だと思います.
上のコードを初めて見て、問題があると思いますが、なぜx＜minStock.peek()の時だけスタックを押しますか?もし、プッシュ(5)、プッシュ(1)、プッシュ(3)のように、minStockには5と1しかないじゃないですか?このようにpop()が1を出したら、getMin()は5をもらえます.3じゃないですか?実はこのように考えるのは間違いです.ポップが出る前に、3はもうポップに出されました. 
minStockの記録は常に現在のすべての要素の中で最小であり、minStock.peek()がStockの中で位置しているに関わらず.
【Stock内蔵せずに実現】
来た:https://oj.leetcode.com/discuss/15651/my-java-solution-without-build-in-stack

class MinStack {
    Node top = null;

    public void push(int x) {
        if (top == null) {
            top = new Node(x);
            top.min = x;
        } else {
            Node temp = new Node(x);
            temp.next = top;
            top = temp;
            top.min = Math.min(top.next.min, x);
        }
    }

    public void pop() {
        top = top.next;
        return;
    }

    public int top() {
        return top == null ? 0 : top.val;
    }

    public int getMin() {
        return top == null ? 0 : top.min;
    }
}

class Node {
    int val;
    int min;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

Python版の解題報告:[LeetCode]Min Stock in Python