[LeetCode] 155. Min Stack

Posted on | In

Problem

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:

1
2
3
4
5
6
7
8
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.

Explanation 1

  1. Creat two stack s1 and s2. s1 is used to like a normal stack to store the elements. s2 is used to stroing the min element.

  2. In s2, if the pushing element is smaller or equal than the s2’s top element, that means we have a new min element, so we push this element to s2 too. Else, if the pushing element is greater than s2’s top element, we don’t push that into s2, since it doesn’t change the min if we pop it in the future.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MinStack {

    /** initialize your data structure here. */
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();

    public MinStack() {
    }

    public void push(int x) {
        s1.push(x);
        if (s2.isEmpty() || x <= s2.peek()) s2.push(x);
    }

    public void pop() {
        int temp = s1.pop();
        if (!s2.isEmpty() && temp == s2.peek()) s2.pop();
    }

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Explanation 2

  1. We can also use only stack to solve this problem, but now, we also need a variable or pointer called min that equals to the minimum element. Initialilly, min set to the largest integer.

  2. When we push an element, we compare min and the element that get push x. If x is smaller or equal to min, then we first push the min then update the min, then push x. We first push the min because that min represents the previous min. When we later pop element, we don’t want the min goes entirely away, we want min to update to the previous min. Else if the element we are pushing is greater than min, then we just normally push x to the stack.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MinStack {

    /** initialize your data structure here. */
    private Stack<Integer> s1 = new Stack<>();
    private int min = Integer.MAX_VALUE;

    public MinStack() {
    }

    public void push(int x) {
        if (x <= min) {
            s1.push(min);
            min = x;
        }
        s1.push(x);
    }

    public void pop() {
        int temp = s1.pop();
        if (temp == min) min = s1.pop();
    }

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

    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */