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.
这个我想了很久，其实挺简单的，你可以发挥你的想象使用任何方法来实现这么一个Min Stack，而我的思想局限在了使用数组，栈这些常见的数据结构上。我们完全可以抛弃这些。
使用一个自定义类，这个类来代表栈里的每一个元素，这个类有三个属性：val，min，down。
val代表当前元素的值
min代表当前栈里最小的值是多少
down代表谁在这个元素下面
每次压栈时，我都可以把当前的元素的值和栈里最小的值做对比得到新的最小值。
public class MinStack {
private Item head = null;
public MinStack() {}
public void push(int x) {
if (head==null)
head = new Item(x,x,null);
else
head = new Item(x,x>head.min?head.min:x,head);
}
public void pop() {
head = head.down;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
private class Item {
public int val;
public int min;
public Item down;
public Item(int val,int min,Item down) {
this.val = val;
this.min = min;
this.down = down;
}
}
}
