针对王道考研第三章（栈与队列）的拓展思考题–最小栈的实现。本文会探讨三种方法来实现，分别是辅助类、单个栈和双栈。
题目
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
注：这里要求的是常量级的时间里找到最小值，所以先排序、再查找是不行的，我们必须在需要的时候就要得到最小值
方法一：辅助类（链表类）
思路
我们知道，栈其实是一种操作受限的线性表，所以栈的一些操作可以通过链表来实现。这里要我们设计一个栈，而栈的实现我们可以使用链表，先定义一个链表类。
class ListNode{
public int val;
public int min;
public ListNode next;
public ListNode(int val, int min, ListNode next){
this.val = val;
this.min = min;
this.next = next;
}
}
|
栈中的最小值始终保存在链表的头结点，我们要获取最小值时直接返回head.min，即可在常量时间内完成。
代码实现
public class test{
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(1);
ms.push(2);
ms.push(3);
ms.push(-1);
System.out.println("min:" + ms.getMin());
}
}
class MinStack{
private ListNode head;
public void push(int x){
if(empty()){
head = new ListNode(x, x, null);
}
else
head = new ListNode(x, Math.min(x , head.min), head);
}
public void pop(){
if(empty())
throw new IllegalStateException("栈为空......");
head = head.next;
}
public int getMin(){
if(empty())
throw new IllegalStateException("栈为空......");
return head.min;
}
private boolean empty(){
return head == null;
}
}
class ListNode{
public int val;
public int min;
public ListNode next;
public ListNode(int val, int min, ListNode next){
this.val = val;
this.min = min;
this.next = next;
}
}
|
输出结果：
min：-1
算法主体
class MinStack{
private ListNode head;
public void push(int x){
if(empty()){
head = new ListNode(x, x, null);
}
else
head = new ListNode(x, Math.min(x , head.min), head);
}
public void pop(){
if(empty())
throw new IllegalStateException("栈为空......");
head = head.next;
}
public int getMin(){
if(empty())
throw new IllegalStateException("栈为空......");
return head.min;
}
private boolean empty(){
return head == null;
}
}
class ListNode{
public int val;
public int min;
public ListNode next;
public ListNode(int val, int min, ListNode next){
this.val = val;
this.min = min;
this.next = next;
}
}
|
通过辅助类 ListNode 来实现栈的操作，原理上还是很好懂得，结合了栈与链表相似特性，可能效果不如双栈，但不失为一种方法。
方法二：压缩还原法（单栈）
思路
每一次入栈的元素和上一个元素都会有一个差值，如果入栈元素比上一个大，差值就会为正值，如果比上一个小，差值就会为负。那么我们的栈中只需要存入他们的差值，用一个min辅助变量来存储当前最小值即可。
入栈：
压缩：将要入栈的元素 x 减去当前最小值 min ，得到一个差值 diff ，栈中只储存该差值；
更新：如果入栈的元素 x 比 min 还要小，就更新最小值，min = x;
初始：第一次入栈，栈中没有值，所以令 min = x；
出栈：
- 更新：如果栈中存储的差值 diff 是负数，说明出栈的元素是当前最小值 min ，需要把 min 值更新为上一个最小值 min = min - diff ，否则，出栈的元素不是最小值，则不对 min 变量做任何操作；
- 还原：如果栈中存储的差值diff是正数，说明 top = min + diff，否则，说明top元素本身是最小值 top = min；
代码实现
import java.util.Stack;
public class test{
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(1);
ms.push(2);
ms.push(-1);
ms.push(3);
System.out.println("min:" + ms.getMin());
}
}
class MinStack{
Stack<Integer> stack = new Stack<Integer>();
int min;
public void push(int x ){
if(stack.isEmpty()){
min = x;
stack.push(x - min );
}
else {
int diff = x - min;
stack.push(diff);
if(diff < 0 )
min = x;
}
}
public void pop(){
if(stack.isEmpty())
return;
int diff = stack.pop();
if(diff < 0 ){
min = min - diff;
}
}
public int top(){
if (stack.isEmpty())
return -1;
int diff = stack.peek();
if(diff < 0){
return min;
}
return min + diff;
}
public int getMin(){
if (stack.isEmpty())
return -1;
return min;
}
}
|
输出结果：
min：-1
算法主体
class MinStack{
Stack<Integer> stack = new Stack<Integer>();
int min;
public void push(int x ){
if(stack.isEmpty()){
min = x;
stack.push(x - min );
}
else {
int diff = x - min;
stack.push(diff);
if(diff < 0 )
min = x;
}
}
public void pop(){
if(stack.isEmpty())
return;
int diff = stack.pop();
if(diff < 0 ){
min = min - diff;
}
}
public int top(){
if (stack.isEmpty())
return -1;
int diff = stack.peek();
if(diff < 0){
return min;
}
return min + diff;
}
public int getMin(){
if (stack.isEmpty())
return -1;
return min;
}
}
|
只使用一个栈，通过栈存入差值，另外加入辅助变量的方法实现最小值的获取。
方法三：双栈
思路
第三个方法就很简单了，这里我们能用两个栈，那么栈1就用来存放需要压栈的元素，栈2就存放最小值。栈2的栈顶元素就是最小值。主要分清楚两个栈的功能就行。
代码实现
import java.util.Stack;
public class test{
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(1);
ms.push(2);
ms.push(-1);
ms.push(-2);
System.out.println("min:" + ms.getMin());
}
}
class MinStack{
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public int getMin(){
return stack2.peek();
}
public void push(int x){
stack1.push(x);
if(stack2.empty() || x < getMin())
stack2.push(x);
}
public void pop(){
if(stack1.pop() == stack2.peek())
stack2.pop();
}
public int top(){
return stack1.peek();
}
}
|
输出结果：
min：-2
算法主体
class MinStack{
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public int getMin(){
return stack2.peek();
}
public void push(int x){
stack1.push(x);
if(stack2.empty() || x < getMin())
stack2.push(x);
}
public void pop(){
if(stack1.pop() == stack2.peek())
stack2.pop();
}
public int top(){
return stack1.peek();
}
}
|
两个栈的原理简化了很多，但另外两种方法的思想还是值得去研究一下得，可以更好地拓展思路。
