30.包含min函数的栈

题目

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

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.

来源：力扣（LeetCode）

思路

普通栈的 push() 和 pop() 函数的复杂度为 O(1)O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)。

• 本题难点：将min（）函数复杂度降为O（1），通过辅助栈实现

  栈1：作为普通栈使用，push(),pop(),peek(),top()

  栈2: 作为辅助栈存放最小值，push()时，将第一个元素或者小于栈顶元素的压入栈中，pop()时对比栈1和栈2顶部元素如果相等，一起出栈，不相等栈2不需要出栈，因为不影响栈的最小值

代码

class MinStack {
	
	Deque<Integer> stack1;
	Deque<Integer> stack2;

    /** initialize your data structure here. */
    public MinStack() {
    	stack1=new ArrayDeque();
    	stack2=new ArrayDeque();
    }
    
    public void push(int x) {
    	if(stack2.isEmpty()||x<=stack2.peek()) {
    		stack2.push(x);
    	}
    	stack1.push(x);
    }
    
    public void pop() {
    	if(stack1.pop().equals(stack2.peek())) {
    		stack2.pop();
    	}

    }
    
    public int top() {
    	return  stack1.peek();
    }
    
    public int min() {

    	return stack2.peek();
    }
}