Solutions with two stacks

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
class MinStack {
Stack<Integer> nums = new Stack<Integer>();
Stack<Integer> min = new Stack<Integer>();

public void push(int x) {
nums.push(x);
if (!min.empty() && min.peek() < x){
min.push(min.peek());
}else{
min.push(x);
}
}

public void pop() {
if (!nums.empty() && !min.empty()){
nums.pop();
min.pop();
}
}

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

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

Solutions with one stacks

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
40
41
42
43
44
45
46
47
48
49
50
public class MinStack {
long min;
Stack<Long> stack;

/** initialize your data structure here. */
public MinStack() {
stack = new Stack<Long>();
}

public void push(int x) {
if (stack.empty()) {
stack.push(0L);
min = x;
} else {
stack.push(x - min); // the max can be Integer.max_value - Integer.min_value, which will overflow, that's why we need long
min = Math.min(x, min);
}
}

public void pop() {
if (!stack.empty()) {
Long pop = stack.pop();
if (pop < 0) {
min -= pop;
}
}
}

public int top() {
Long peek = stack.peek();
if (peek < 0) {
return (int) min;
} else {
return (int) (min + peek);
}
}

public int getMin() {
return (int) 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();
*/