17_155. 最小栈
题目描述：
解题思路：
一看到常数时间下，取出最小元素，就一直觉得应该用哈希表来存。
看了题解之后，“辅助栈”，建立一个辅助栈，同时和当前的栈进行入栈和出栈的操作，只不过辅助栈用来保存当前栈顶元素，对应的最小值。
相当于解法二中，往栈中存入的不是一个Int数据，而是一个元组，元组中存的是当前的栈顶元素，和对应的最小值，这样更有助于理解。
代码：
辅助栈
//辅助栈
class MinStack {
Deque minStack;
Deque stack;
public MinStack() {
this.stack = new LinkedList();
this.minStack = new LinkedList();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(val, minStack.peek()));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
往栈中存入元组
//往栈中存入元组
class MinStack {
Deque stack;
public MinStack() {
stack = new LinkedList();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new Integer[]{val, val});
}else {
stack.push(new Integer[]{val, Math.min(val,stack.peek()[1])});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/