Week2：包含 min 函数的栈

1️⃣ 题目描述

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

2️⃣ 解题思路

• 分析
  stack的push()和pop()时间复杂度都是O(1)；但是如果想获得stack中最小的元素，需要遍历整个栈，而遍历栈需要创两个栈，时间复杂度和空间复杂度都是O(n)，因此重点就是保证min()的时间复杂度为O(1)

• 思路

  函数	操作
  push()	无返回值，所有元素都push到栈A中；当要push的元素小于等于栈B的栈顶元素 or 栈B为空时，就要将该元素push到栈B中
  pop()	无返回值，如果栈A的栈顶元素和栈B的栈顶元素相同时，A和B都要pop栈顶元素；否则只有栈A需要pop栈顶元素
  top()	有返回值，直接return A.pop()
  min()	有返回值，直接return B.pop()

  创建两个栈A和B

  • push():
    所有元素都push到栈A中；
    当要push的元素小于等于栈B的栈顶元素时，就要将该元素push到栈B中：

    对于这句话要考虑两个问题：

    • ①如果栈B为空怎么办？
      如果栈B为空则无法比较，而且只有一开始的时候栈B才可能为空，因此如果栈B为空，则要把要push的元素push到栈B中
    • ②为什么要push的元素等于栈B的栈顶元素时，要push的元素也要入B栈？
      举个例子：如果要push 2 6 1，那么此时栈A为 2 6 1，栈B为2 1，下一个要push的又是1，此时栈A变成2 6 1 1，这个1也要push到栈B中，栈B变为2 1 1。如果栈B还是2 1，那么如果下一个操作是pop()，那么栈A会变成2 6 1，栈B变成2，下一个操作如果是min()的话，结果就成了2，会出错；这就是所谓的非严格降序（非严格：重复的元素也要添加）

  • pop()
    如果栈A的栈顶元素和栈B的栈顶元素相同时，A和B都要pop(还是2 6 1 1这个例子，如果不都pop，结果会出错，自己画一下)；注意一下，对于这种情况，需要栈B先pop，栈A再pop，不然会出错，自己画一下

    如果不同，只有栈A需要pop栈顶元素

3️⃣ 代码

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        A.push(x);
        if(B.empty()||x<=B.top()){
            B.push(x);
        }
    }
    
    void pop() {
        if(A.top()==B.top()){
            B.pop();
        }
        A.pop();
    }
    
    int top() {
        return A.top();
    }
    
    int min() {
        return B.top();
    }

private:
    stack<int> A,B;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */