【剑指 Offer】包含min函数的栈————刷题日记

难度简单362

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3. //返回最小值但是没有 删除里面的元素哦
minStack.pop(); //移除栈顶的元素
minStack.top(); --> 返回 0. //查看 栈顶的元素
minStack.min(); --> 返回 -2. // 返回最小值但是没有 删除里面的元素哦

其实一个栈就是 原始栈。没什么区别，因为这道题只是多了一个min 方法而已，只需要解决这个方法就行了，使用双端队列解决这个方法，最小的元素永远放在第一个，保证每次peek 都是最小值

下面是难点吧

deque.peek()>=x  保证都是最小的，如果不是最小的根本不需要放进双端队列（很重要的思路）
举例子  -2 0 -3   先进来 肯定是-2 ，0 不需要放进来   -3 放到（栈顶和双端队列）第一位。
如果你疑问 要是 删除了-2 -3 要求最小值 0 呢，根本不存在这样阿情况，因为 如果0是最后删除，那意味着肯定第一个进来  （因为栈是先进后出的原则）
所以矛盾了吧，所以呢，0 肯定在其中一个最小值之前删除，所以按照上面例子0也不会进入双端队列。

class MinStack {

     private Stack stackA;
     private Deque deque;
     public MinStack() {
        stackA= new Stack<>();
        deque=new LinkedList<>();
    }

    public void push(int x) {
          stackA.push(x);
        if(deque.isEmpty() || deque.peek()>=x){
            deque.addFirst(x);
        }
    }

    public void pop() {
        int pop = stackA.pop();
        if (pop==deque.peek()){
            deque.removeFirst();
        }
    }

    public int top() {
         return  stackA.peek();
    }

    public int min() {
            return deque.peek();
    }
}