题目

题解

两个类似的方法，一个是使用辅助栈存当前的最小值，一个是直接用一个栈保存一个pair，包括原值和最小值，个人感觉后一种方法更加直观，即方法1 看了下题解还有第三种方法，这个方法只需要一个栈和一个变量存最小值，具体见题解3

1. 单栈双值法

  • 时间复杂度$O(1)$
  • 空间复杂度$O(n)$
class MinStack {
    stack<pair<int,int>> s;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        if(s.size()==0) s.push({x,x});
        else s.push({x,std::min(x, s.top().second)});
    }
    
    void pop() {
        s.pop();
    }
    
    int top() {
        return s.top().first;
    }
    
    int getMin() {
        return s.top().second;
    }
};

/**
 * 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->getMin();
 */

2. 双栈法

  • 时间复杂度$O(1)$
  • 空间复杂度$O(n)$
class MinStack {
    stack<int> s;
    stack<int> min_s;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        if(s.size()==0){
            s.push(x);
            min_s.push(x);
        }else{
            s.push(x);
            min_s.push(std::min(x,min_s.top()));
        }
    }
    
    void pop() {
        s.pop();
        min_s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return min_s.top();
    }
};

/**
 * 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->getMin();
 */

3. 单栈单值法

这个方法用一个栈，但是栈中要在每个最小值的下面多存一个数保存次小值，当最小值已经出栈之后就把次小值放到min_val中

  • 时间复杂度$O(1)$
  • 空间复杂度$O(n)$
 class MinStack {
    stack<int> s;
    int min_val;
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        if(s.size()==0){//第一个数字，在栈中存两遍，并更新min_val，这一步是为了在只有一个值pop()时不会报错
            s.push(x);
            min_val = x;
        }else if(x<=min_val){//新x小于等于min_val，把min_val压入栈中，再存x，更新min_val
            s.push(min_val);
            min_val = x;
        }
        //其他情况直接存x
        s.push(x);
    }
    
    void pop() {
        if(min_val == s.top()){//若取出的数是最小值，则将其下面存的次小值放入min_val，再将该值弹出
            s.pop();
            min_val = s.top();s.pop();
        }else{//其他情况直接出栈
            s.pop();
        }
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return min_val;
    }
};

/**
 * 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();
 */