155 Min Stack

155. Min Stack

1. Question

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
MinStack minStack = new MinStack();
2
minStack.push(-2);
3
minStack.push(0);
4
minStack.push(-3);
5
minStack.getMin(); --> Returns -3.
6
minStack.pop();
7
minStack.top(); --> Returns 0.
8
minStack.getMin(); --> Returns -2.
Copied!

2. Implementation

思路:这题主要注意的是对于push()和pop()两种操作中,当我们发现min时该怎么办。当栈顶是min时,我们需要在pop了min后,可以立马知道当前min应该变为哪个数,所以我们的想法是每当我们发现当前的元素比min小时,我们立马将min压栈,然后更新min值。这样的好处是,当我们call pop()时,如果栈顶的元素等于min, 我们可以很快的知道min应该更新为哪个数
1
class MinStack {
2
int min;
3
Stack<Integer> stack;
4
5
/** initialize your data structure here. */
6
public MinStack() {
7
min = Integer.MAX_VALUE;
8
stack = new Stack<>();
9
}
10
11
public void push(int x) {
12
if (x <= min) {
13
stack.push(min);
14
min = x;
15
}
16
stack.push(x);
17
}
18
19
public void pop() {
20
if (stack.peek() == min) {
21
stack.pop();
22
min = stack.pop();
23
}
24
else {
25
stack.pop();
26
}
27
}
28
29
public int top() {
30
return stack.peek();
31
}
32
33
public int getMin() {
34
return min;
35
}
36
}
37
38
/**
39
* Your MinStack object will be instantiated and called as such:
40
* MinStack obj = new MinStack();
41
* obj.push(x);
42
* obj.pop();
43
* int param_3 = obj.top();
44
* int param_4 = obj.getMin();
45
*/
Copied!

3. Time & Space Complexity

所有操作的时间复杂度都是O(1), 空间复杂度为O(n), n是minStack当前存储的元素个数