day15 最小栈

前两天家里人生病，回去探望了一下。

读题

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

思路

仍然是实现类型的题目，知道栈是什么应该就好写。要求里的这一点可能比较难：能在常数时间内检索到最小元素。
要用什么数据结构实现这个栈？用 vector 吗？其他操作都可以实现，但是如何在常数时间内获取最小元素？事先保存吗？

class MinStack {
private:
    vector<int> stack;
    int min;

public:
    MinStack() {
       min=-114514;
    }
    
    void push(int val) {
        stack.push_back(val);
        if(min==-114514 || val<min){
            min=val;
            return;
        }
    }
    
    void pop() {
        if(*(stack.end()-1)==min){
            min=stack[0];
            for (auto it = stack.begin(); it != stack.end()-1; ++it) {
                if(*it<min) min=*it;
            }
        }
        stack.erase(stack.end()-1);
    }
    
    int top() {
        return *(stack.end()-1);
    }
    
    int getMin() {
        return min;
    }
};

提交，发现有点小问题，输出不对：

输出
[null,null,null,null,2147483647,null,2147483646,null,2147483646,null,null,2147483647,2147483646,null,-2147483648,-2147483648,null,2147483647]

预期结果
[null,null,null,null,2147483647,null,2147483646,null,2147483646,null,null,2147483647,2147483647,null,-2147483648,-2147483648,null,2147483647]

检查之后增加了空栈检查和引入了 climits 库，还用了.back() 这种相对规范的写法。

有代码：

#include <climits> 

class MinStack {
private:
    vector<int> stack;
    int min;

public:
    MinStack() {
       min=INT_MAX;
    }
    
    void push(int val) {
        stack.push_back(val);
        if(val<min){
            min=val;
            return;
        }
    }
    
    void pop() {
        if (stack.empty()) {
            return;
        }
        if(stack.back()==min){
            min=INT_MAX;
            for (auto it = stack.begin(); it != stack.end()-1; ++it) {
                if(*it<min) min=*it;
            }
        }
        stack.pop_back();
    }
    
    int top() {
        if (stack.empty()) {
            return INT_MIN;
        }
        return stack.back();
    }
    
    int getMin() {
        if (stack.empty()) {
            return INT_MIN;
        }
        return min;
    }
};

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

结果

通过了，0ms，22.57 MB 内存，比较领先的结果。

官方题解

方法一：辅助栈

使用一个栈来保存每个元素对应的最小值。而我的是只有一个数字来保存，所以每次出栈都需要遍历一下，更新最小值，属于是投机取巧的做法。
另外，直接使用了 stack 数据类型，而不是 vector。

收获

复习了栈的定义和 vector 的操作。虽然我过了但是是投机取巧的做法，正经做还是得空间换时间。
这题感觉有点无聊，何况是允许使用 stack 实现 stack。为啥会是中等？
注意到题解里写的是简单，感觉真实难度也确实是简单。