# 最小栈 Min Stack

## 题目

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:

``````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.
``````

## 思路&题解

``````class MinStack {

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

public void push(int x) {
if(stack.isEmpty()){
stack.push(x);
stack.push(x);
} else {
int top = stack.peek();
stack.push(x);
stack.push(x>top?top:x);
}
}

public void pop() {
stack.pop();
stack.pop();
}

public int top() {
int top = stack.pop();
int value = stack.pop();
push(value);
return value;
}

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

## 知识点分析

1. 入栈调整：每次入栈，需要同时将新元素和新栈的当前最小元素入栈，栈顶用于放最小元素
2. 出栈调整：每次出栈，需要连续出两次，将元素和最小元素都弹出
3. 取栈顶调整：每次取栈顶，需要先把最小元素弹出，然后再取元素，拿到元素后还需要把他再次入栈，这一步可以调用实现的入栈操作（一次入栈两个元素）。
4. 取最小值：获取栈顶的元素，即为最小值