设计一个支持 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.

解题思路

方法一：在栈里的节点 Node 里维护 min 值， 每次新进一个节点，该节点的 min 都是当前最小

方法二：维护两个栈，一个栈正常操作，另一个栈专门用来存最小值，也就是新进来的节点最小，那就进最小栈，否则不进。

Java实现

方法一

class MinStack {
	class Node{
		int val;
		int min;
		Node next;
		public Node(int val, int min) {
			this.val = val;
			this.min = min;
		}
	}
	Node top;
	public MinStack() {
	}
	
	public void push(int val) {
		if (top == null){
			top = new Node(val, val);
			return;
		}
		Node newTop = new Node(val, Math.min(top.min, val));
		// 让新进节点成为栈顶节点 
		newTop.next = top;
		top = newTop;
	}
	
	public void pop() {
		top = top.next;
	}
	
	public int top() {
		return top.val;
	}
	
	public int getMin() {
		return top.min;
	}
}

方法二：

class MinStack {
	Stack<Integer> stack;
	Stack<Integer> minStack;

	public MinStack() {
		stack = new Stack<>();
		minStack = new Stack<>();
	}

	public void push(int val) {
		if (stack.isEmpty()){
			stack.push(val);
			minStack.push(val);
			return;
		}
		if (val <= minStack.peek()){
			stack.push(val);
			minStack.push(val);
		} else {
			stack.push(val);
		}
	}

	public void pop() {
		if (Objects.equals(stack.peek(), minStack.peek())){
			stack.pop();
			minStack.pop();
		} else {
			stack.pop();
		}
	}

	public int top() {
		return stack.peek();
	}

	public int getMin() {
		return minStack.peek();
	}
}