链接

代码：

class MinStack {
private:stack<int> f,s;
public:MinStack(){}void push(int val) {s.push(val);if(f.empty()||val<=f.top()){f.push(val);}}void pop() {if(s.top()<=f.top())f.pop();s.pop();}int top() {return s.top();}int getMin() {return f.top();}
};

题解：这个题意还是比较难懂，代码写起来很简单，我们定义类的私有变量s作为存储数据的栈，然后为了常数时间内返回栈中最小元素，所以我们还定义了一个栈 f。f[i] 即：与之对应的s栈中目前最小的元素，但是我们还做了一个优化：如果你push进s栈一个很大的元素，我们 f 栈没必要动弹，因为我们f 记录的是最小元素。怎么判断？你push进s栈的元素如果小于等于f 的栈顶，我才在f 栈加一个元素。否则我f 栈什么都不做。

pop的时候也一样，pop的元素如果大于我的栈顶元素，那f 栈就不必更新什么。反之，如果你pop的元素小于等于f 栈顶元素，那么说明我之前记录过，所以f 也要pop。