155.Min Stack

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.