155. 最小栈

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

示例: 输入： ["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. 提示： pop、top 和 getMin 操作总是在 非空栈 上调用。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/min-stack 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一

通过设计两个栈来存放数据，一个是正常入队序列，另一个是经过比较后，入队的最小值。不管入队还是出队都需要同时操作两个栈。

class MinStack { //存放正常数据 private Stack<Integer> stack; //存放最小数据 private Stack<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x) { stack.push(x); if(minStack.isEmpty()){ minStack.push(x); }else{ //minStack.push(Math.min(x, minStack.peek())); minStack.push(x <= minStack.peek() ? x : 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(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

思路二

通过创建一个虚拟头节点来保存当前值、最小值以及下一个值的指向。

当第一个值入队的时候，前面有一个虚拟头节点，最小值为无穷大∞，这样在进行第一个数入队的时候，存放自己为当前的最小值。

这样设计的话，没有使用栈，使用自己创建的链表，不论进行什么操作，都可以通过头节点来判断。减少了时间复杂度。

class MinStack { private static class Node{ public int val; public int min; public Node next; public Node (int val, int min, Node next){ this.val = val; this.min = min; this.next = next; } } private Node head; public MinStack() { head = new Node(0, Integer.MAX_VALUE, null); } public void push(int x) { head = new Node(x, Math.min(x, head.min), head); } public void pop() { head = head.next; } public int top() { return head.val; } public int getMin() { return head.min; } } /** * 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(); */