155.Min Stack

Posted on | In

Test cases

1
2
3
4
5
6
7
8
["MinStack","push","push","push","push","pop","getMin","pop","getMin","pop","getMin"]
[[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]]
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
["MinStack","push","push","push","getMin","pop","getMin"]
[[],[0],[1],[0],[],[],[]]
["MinStack","push","push","push","top","pop","getMin","pop","getMin","pop","push","top","getMin","push","top","getMin","pop","getMin"]
[[],[2147483646],[2147483646],[2147483647],[],[],[],[],[],[],[2147483647],[],[],[-2147483648],[],[],[],[]]

Solution 1: accepted 111ms

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
class MinStack {
    private Stack<Integer> master;    
    private Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        master = new Stack<>();    
        min = new Stack<>();
    }
    
    public void push(int x) {
        master.push(x);
        if (min.size() == 0 || min.peek() >= x) {  // >= rather than >, there could be multiple minimum values
            min.push(x);
        }
    }
    
    public void pop() {
        if (master.pop().equals(min.peek())) {  // Integer, use equals not ==
            min.pop();
        }
    }
    
    public int top() {
        return master.peek();   
    }
    
    public int getMin() {
        return min.peek();    
    }
}

Follow-up:

If the given numbers have a lot of duplicates, how to optimize the space use of the min stack?
We now maintain <number, the index of the number when it's added> in the min stack and we only pop it when the current index is equal or smaller than the index of the top element in the min stack. As a result, we also need a int count to track the index.