【剑指offer】面试题30：包含 min 函数的栈

﹏ヽ暗。殇╰゛Y 2022-03-29 03:46 137阅读 0赞

> **题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素 min 函数。在栈中，调用 min、push、及 pop 的时间复杂度都是O(1)。**

我们可以使用两个栈，一个数据栈，另一个为辅助栈。辅助栈用于存放最小元素和每次压栈时的次小元素（之前的最小元素和新压入栈的元素两者之间的最小值或相等）。

如果每次都把最小元素压入辅助栈，那么就能保证辅助栈顶一直都是最小元素。当最小元素从数据栈中被弹出后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小元素。

下面看个案例再了解下这个过程：

步骤1：首先往空的数据栈中压入数字3，显然现在3是最小值，则也在辅助栈中压入3；

步骤2：往数据栈中压入数字4，由于4大于之前的最小值，因此仍然往辅助栈中压入3；

步骤3：往数据栈中压入数字2，由于2小于之前的最小值3，因此把最小值更新为2，并把2压入辅助栈；

步骤4：往数据栈中压入数字1，由于1小于之前的最小值2，因此把最小值更新为1，并把1压入辅助栈；

步骤5：弹出数据栈中的1，辅助栈的栈顶元素1也随之弹出，则此时辅助栈的栈顶元素为2；

步骤6：弹出数据栈中的2，辅助栈的栈顶元素2也随之弹出，则此时辅助栈的栈顶元素为3；

步骤7：往数据栈中压入数字0，由于0小于之前的最小值3，因此把最小值更新为0，并把0压入辅助栈。

..........

将上面的过程翻译成代码即为：

public class MinStack {
    
    	Stack<Integer> dataStack = new Stack<Integer>();  // 数据栈
    	Stack<Integer> minStack = new Stack<Integer>();   // 辅助栈
    	
    	public void push(int node){
    		dataStack.push(node);     // 压进数据栈
    		if(minStack.isEmpty() || node < minStack.peek()){
    			minStack.push(node);  // 压进辅助栈
    		}else{
    			// 如果要压进数据栈的元素比当前最小值大，则将最小值再压入辅助栈一次
    			minStack.push(minStack.peek());
    		}
    	}
    	
    	public void pop(){
    		dataStack.pop();
    		minStack.pop();
    	}
    	
    	public int top(){
    		return dataStack.peek();
    	}
    	
    	public int min(){
    		return minStack.peek();
    	}
    }