设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。实现 MinStack 类MinStack 初始化堆栈对象。对应操作码为0。void pushint val 将元素val推入堆栈。对应操作码为1。void pop 删除堆栈顶部的元素。对应操作码为2。int top 获取堆栈顶部的元素。对应操作码为3。int getMin 获取堆栈中的最小元素。对应操作码为4。inp

算法1

用一个辅助栈来记录最小值，每次 push 时如果当前值小于等于辅助栈的栈顶元素，则将当前值也 push 到辅助栈中，pop 时如果 pop 的元素等于辅助栈的栈顶元素，则同时 pop 辅助栈的栈顶元素。getMin 直接返回辅助栈的栈顶元素即可。

时间复杂度

push/pop/top/getMin 操作都是 O(1) 的。

C++ 代码

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

}

void push(int val) {
    s1.push(val);
    if (s2.empty() || val <= s2.top()) {
        s2.push(val);
    }
}

void pop() {
    if (s1.top() == s2.top()) {
        s2.pop();
    }
    s1.pop();
}

int top() {
    return s1.top();
}

int getMin() {
    return s2.top();
}

private: stack s1, s2; };

算法2

用一个元素栈和一个辅助栈来实现，辅助栈用于记录最小值。每次 push 时，先将元素 push 到元素栈中，然后判断辅助栈的栈顶元素是否大于等于当前元素，如果是，则将当前元素 push 到辅助栈中。pop 时，如果元素栈顶元素等于辅助栈的栈顶元素，则同时 pop 元素栈和辅助栈的栈顶元素。getMin 直接返回辅助栈的栈顶元素即可。

时间复杂度

push/pop/top/getMin 操作都是 O(1) 的。

C++ 代码

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

}

void push(int val) {
    s1.push(val);
    if (s2.empty() || val <= s2.top()) {
        s2.push(val);
    }
}

void pop() {
    if (s1.top() == s2.top()) {
        s2.pop();
    }
    s1.pop();
}

int top() {
    return s1.top();
}

int getMin() {
    return s2.top();
}

private: stack s1, s2; }