题目

设计一个支持 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 次# 思路

思路

首先，理解题目意思，有两个目的

• 实现栈功能
• 可以通过getMin获取到 栈 中的 最小值

辅助栈

在这里，这个最小值的获取，便使用栈去承载这个最小值，使用minStack表示
实际元素的存储的栈使用stack表示

栈先进后出，只要stack中有有元素出栈，则对应的这个最小值minstack栈，也要出栈，

其出栈后，minstack栈内的第一个元素，还是stack栈里面的最小值，示例如下

// 初始值 stack：null minStack：INT_MAX // -2入栈 stack：-2 minStack：INT_MAX，-2 // 0入栈 stack：-2，0 minStack：INT_MAX，-2，-2 // -3入栈 stack：-2，0，-3 minStack：INT_MAX，-2，-2，-3

Deque中用于栈操作（入栈、出栈、查看栈顶）的核心方法说明：

• 入栈：push(E e)：将元素压入栈顶（即添加到Deque的头部，遵循 LIFO 原则）
• 出栈：pop()：移除并返回栈顶元素（即Deque的头部元素，遵循 LIFO 原则）
• 查看栈顶元素（不移除）：peek()：获取栈顶元素（即Deque的头部元素），但不移除该元素

单向链表

使用Node去存储这个过程，每个节点对应栈里的一个元素，同时携带了当前栈的最小值信息：

• key：存入栈的元素本身的值，供top()方法返回栈顶元素
• value：从栈底到当前节点为止，栈内的最小值，供getMin()方法直接返回
• next：指向下一个节点（栈中更靠下、更早入栈的元素）

整个栈用单链表的头部作为栈顶：

• 入栈 = 链表头插法，新节点插在最前面
• 出栈 = 链表头删法，直接把头指针后移一位
• 所有操作都是 O (1) 时间

classNode{intkey;intvalue;Nodenext;publicNode(intkey,intvalue){this.key=key;this.value=value;this.next=null;};publicNode(intkey,intvalue,Nodenode){this.key=key;this.value=value;// 反向this.next=node;}}

注意：

• 入栈时，更新的是当前这整个链表，即node=newNode，而非node.next=newNode
• 出栈时，node=node.next;

// 初始值 in：null node：null // -2入栈 stack：-2 node：{-2,-2} // 0入栈 stack：-2，0 node：{0,-2}，{-2,-2} // -3入栈 stack：-2，0，-3 node：{-3,-3}，{0,-2}，{-2,-2} // getMin() // pop() stack：-2，0 node：{0,-2}，{-2,-2}

算法

辅助栈

classMinStack{Deque<Integer>stack;Deque<Integer>minStack;publicMinStack(){stack=newLinkedList<>();minStack=newLinkedList<>();minStack.push(Integer.MAX_VALUE);}publicvoidpush(intval){stack.push(val);minStack.push(Math.min(minStack.peek(),val));}publicvoidpop(){stack.pop();minStack.pop();}publicinttop(){returnstack.peek();}publicintgetMin(){returnminStack.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(); */

单向链表

classMinStack{Nodenode;publicMinStack(){}publicvoidpush(intval){if(node==null){node=newNode(val,val);}else{intmin=Math.min(node.value,val);NodenewNode=newNode(val,min,node);node=newNode;}}publicvoidpop(){node=node.next;}publicinttop(){returnnode.key;}publicintgetMin(){returnnode.value;}classNode{intkey;intvalue;Nodenext;publicNode(intkey,intvalue){this.key=key;this.value=value;this.next=null;};publicNode(intkey,intvalue,Nodenode){this.key=key;this.value=value;this.next=node;}}}/** * 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(); */