主要是为了实现getMin函数
题目
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
伪单栈解决
压入和弹出时都同时压入推出最小值,检索时最小值在栈顶
class MinStack {
stack<int> s;
int minV=INT_MAX;
public:
MinStack() {
}
void push(int val) {
s.emplace(minV);
minV=val>minV?minV:val;
s.emplace(val);
// minV=min(val,minV);
}
void pop() {
// if(!s.empty()){
s.pop();
minV=s.top();
s.pop();
// }
}
int top() {
// if(!s.empty()){
return s.top();
// }
}
int getMin() {
// if(!s.empty()){
return minV;
// return minV;
}
};
单栈,不消耗额外空间
栈内存放与最小值的差值,压入和弹出判断差值正负,如为负则更新最小值:压入时min=压入值,弹出时min=val-差值;
注意储存差值时范围会大于int的范围
class MinStack {
long min=INT_MAX;
stack<long> s;
public:
MinStack() {}
void push(int val) {
long d=val-min;
s.emplace(d);
min=d<0?val:min;
}
void pop() {
long t=s.top();
min=t<0?min-t:min;
s.pop();
}
int top() {
long t=s.top();
return t>0?t+min:min;
}
int getMin() {
return min;
}
};