解题过程:
1.两个栈,一个正常栈,一个记录最小值的栈
2.为了方便,最小栈stk2预先压入INT_MAX
3.push的时候,stk1正常压入,stk2根据自己的栈顶和val压入较小值
4.pop和top正常pop和top
5.getMin返回tk2的栈顶
6.空间复杂度,维护记录最小值的栈需要O(N)的空间。
class MinStack {
public:
MinStack() {
stk2.push(INT_MAX);
}
void push(int val) {
stk1.push(val);
stk2.push(min(stk2.top(),val));
}
void pop() {
stk1.pop();
stk2.pop();
}
int top() {
return stk1.top();
}
int getMin() {
return stk2.top();
}
private:
stack<int>stk1,stk2;
};