包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

分析

第一遍尝试时忽略了pop操作，pop操作会把最小值弹出。

我这里使用了双栈

• push操作的同时对元素进行检查
• pushMin将最小值更新，保持peek为最小值
• 当使用pop操作时需要检查是否将最小值弹出
• 如果最小值被弹出，min也应该弹出对应值
• min.peek时刻保持当前栈中最小值

注意：本代码忽略当栈为空的时候

代码

import java.util.Stack;

public class Solution {

    private Stack<Integer> min  = new Stack();
    private Stack<Integer> stack = new Stack();
    
    public void push( int node ){
        stack.push(node);
        pushMin(node);
    }
    
    public void pushMin(int node){
        if( min.isEmpty() || node <= min.peek() ){
            min.push(node);
        }
    }
    
    public void popMin( int node ){
        if( node == min.peek() ){
            min.pop();
        }
    }
    
    public int pop(){
        int pop = stack.pop();
        popMin(pop);
        return pop;
        
    }
    
    public int top(){
        return stack.peek();
    }
    
    public int min(){
        return min.peek();
    }
}