155. 最小栈

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：
-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

分析：常规的push、pop、top这样的方法很好实现，只需要一个栈类型对象即可，但是getMin获取最小值想保持O(1)的复杂度就需要自己设计一个合理的方案来解决查询的问题

思路一：用双栈来处理，一个用来存储正常数据，另一个用来专门存储最小值；两个栈入栈出栈保持一致

class MinStack {
    
    private Stack<Integer> stack;//普通存放数据的栈
    private Stack<Integer> minStack;//存放最小值得栈

    public MinStack() {
       stack = new Stack();
       minStack = new Stack();
    }
    
    public void push(int val) {
       if(minStack.isEmpty()){
           minStack.push(val);
       }else {
         minStack.push(Math.min(val,minStack.peek()));
       }
       stack.push(val);
    }
    
    public void pop() {
       stack.pop();
       minStack.pop();
    }
    
    public int top() {
       return stack.peek();
    }
    
    public int getMin() {
       return minStack.peek();
    }

}

思路二：用链表来存储数据和对应的最小值，每个最小值的结点都被放在头部，也就是当做头节点来用；

class MinStack {

    //链表头结点
    ListNode head;

    public MinStack() {
       //初始化 (最小值用最大值表示就可以保证接下来存的是真正的最小值)
       head = new ListNode(0,Integer.MAX_VALUE,null);
    }
    
    public void push(int val) {
       head = new ListNode(val,Math.min(val,head.min),head);
    }
    
    public void pop() {
      head = head.next;
    }
    
    public int top() {
      return head.val;
    }
    
    public int getMin() {
       return head.min;
    }

    private static class ListNode {
        public int val;
        public int min;
        public ListNode next;
        ListNode(int val,int min,ListNode next){
          this.val = val;
          this.min = min;
          this.next = next;
        }
    }
     
}