包含min函数的栈

题目链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

image.png

思路解题
这道题目一共有三个点：

1. 实现正常的数据出入栈；
2. 实现最小数的栈记录；
3. 要求时间复杂度O(1)；

针对这三个点进行拆解：

1. 就正常的栈数据结构就可以进行数据，记为A；
2. 如果不考虑时间复杂度我们可以进行另外一个辅助栈（计为B）入栈的时候排序，但是我们需要结合第三点考虑时间复杂度为O(1)。这个时候采取的策略结合两个栈进行处理判断：
   2.1 push的判断一下当前这个值和B里面的peek值，如果是小于这个peek值的话，那么就入栈B,这样就把B维护为了一个降序排序的顺序;
   2.2 pop的时候就用A的pop值和B的peek值判断，如果这两个值相等，那么B也要pop;
   2.3 min的时候取A和B的peek值判断谁小就返回谁。

代码如下

class MinStack {
        Deque<Integer> A, B;

        /** initialize your data structure here. */
        public MinStack() {
            A =  new LinkedList<>();
            B =  new LinkedList<>();
            B.push(Integer.MAX_VALUE);
        }

        public void push(int x) {
            A.push(x);
            if (x <= B.peek()){
                B.push(x);
            }
        }

        public void pop() {
            int data = A.pop();
            if (data == B.peek()){
                B.pop();
            }
        }

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

        public int min() {
            int aMin = A.peek();
            int bMin = B.peek();
            return  aMin< bMin?aMin:bMin;
        }
    }