Leetcode: Min Stack

By | 2018 年 7 月 23 日

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.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Analysis

For O(1) pop, push, a normal stack can serve this purpose. But a little hard for O(1) get min.

However, noticed that this is still a stack, can not just pop node with min value. So we can record min value on each node when pushing into this stack.

e.g. as the example above:

  1. push -2
    -2(-2) — means the node has value -2 and the min value as of now in the stack is -2.
  2. push 0
    0(-2) -> -2(-2)
  3. push -3
    -3(-3) -> 0(-2) -> -2(-2)
  4. getMin return -3 (in the parenthesis)
  5. pop
    0(-2) -> -2(-2)
  6. top, return 0
  7. getMin return -2

Solutions

Java

class MinStack {

    class Node {
        public int value;
        public Node min;
        public Node next;
        public Node(int val){
            this.value = val;
        }
    }

    Node head;

    /** initialize your data structure here. */
    public MinStack() {
        head = new Node(0);
    }

    public void push(int x) {
        Node newNode = new Node(x);
        newNode.next = this.head.next;
        this.head.next = newNode;
        newNode.min = newNode.next != null && newNode.next.min.value < newNode.value ? newNode.next.min : newNode;
    }

    public void pop() {
        if(this.head.next != null) {
            this.head.next = this.head.next.next;
        }
    }

    public int top() {
        if(this.head.next != null) {
            return this.head.next.value;
        } else {
            return Integer.MAX_VALUE;
        }
    }

    public int getMin() {
        if(this.head.next != null) {
            return this.head.next.min.value;
        } else {
            return Integer.MAX_VALUE;
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注