数据结构学习 jz30 包含 min 函数的栈

关键词：排序

题目：最小栈

方法一：在记录这个数的同时，记录目前的最小值。看了提示才写出来的。

方法二：辅助栈。辅助栈保持非严格递减。看了k神的答案。

方法一：

一开始没想到怎么存最小，看了评论的提示才想到的。

思路：

关键：一个栈的一个元素存两样大小：这个数本身，包括这个数在内，目前栈的最小值。

存数的同时存截至到这个数为止的最小数。

注意：min的比较是和栈的前一个min比，不是和全局的min比。

min=(x<stack.back()[1])?x:stack.back()[1];

如果全局的min是1，可是1已经被pop了，但是这个min的记录还会是1，就会出错。

复杂度计算：

时间复杂度O(n)

空间复杂度O(n)

代码：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        if(stack.empty()) 
            min=x;
        else
            min=(x<stack.back()[1])?x:stack.back()[1];
        stack.push_back({x,min});
    }
    
    void pop() {
        stack.pop_back();
    }
    
    int top() {
        return stack.back()[0];
    }
    
    int getMin() {
        return stack.back()[1];
    }
private:
    vector<vector<int>> stack;
    int min=INT_MAX;
};

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

方法二：

看了k神。用了两个栈，A栈正常存数，B栈存最小值，B栈要保持非严格递减。

思路：

入栈的时候，还需要维护辅助栈。为什么要维护非严格降序的辅助栈：

1、如果：

B.top() >= x

则要把x存进B里面，保持非严格降序，这个时候x就是B里面最小的。

2、如果：

B.top() < x

?则不用存x，因为前面已经有B.top()小于x了，x无论怎么样都不可能是最小值。

出栈的时候，如果B.top()等于要A出栈的那个数，那么B也要跟着出栈。理由当然是因为那个数跑了，所以B当然要一起删掉。

非严格降序：

复杂度计算：

时间复杂度O(n)

空间复杂度O(n)

代码：

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 getMin() {
        return B.top();
    }
private:
    stack<int> A;
    stack<int> 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->getMin();
 */