目录
1.题目
https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/description/
请你设计一个 最小栈 。它提供
push，pop，top操作，并能在常数时间内检索到最小元素的栈。实现
MinStack类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。示例 1：
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(2); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
-2^31 <= val <= 2^31 - 1pop、top和getMin操作总是在 非空栈 上调用push、pop、top和getMin最多被调用3 * 10^4次注意：本题与主站 155 题相同：155. 最小栈 - 力扣（LeetCode）
2.分析
如果使用C++ STL库中的stack模版,能大大简化代码,主要的问题在于能在常数时间内检索到最小元素
容易想到以下错误写法:
class MinStack {
public:
/** initialize your data structure here. */
MinStack()
{}
void push(int x)
{
st.push(x);
if (x<min)
min=x;
}
void pop() //有可能会删最小元素
{
st.pop();
}
int top()
{
return st.top();
}
int getMin()
{
return min;
}
private:
stack<int> st;
int min=INT_MAX;
};
严格来说,栈不允许遍历,如果栈顶恰好是最小元素,现执行pop()会找不到下一个不在栈顶上的最小元
例如:
方法1:记录最小元素的出现顺序
最小元素的出现顺序符合FILO的规则,因此可以用栈来记录最小元素的更新记录
class MinStack {
public:
MinStack()
{
min_order.push(INT_MAX);
}
void push(int x)
{
st.push(x);
if (x<=min_order.top())
{
min_order.push(x);
}
}
void pop() //有可能会删最小元素
{
if (st.top()==min_order.top())
min_order.pop();
st.pop();
}
int top()
{
return st.top();
}
int getMin()
{
return min_order.top();
}
private:
stack<int> st;
stack<int> min_order;
};注意:push中的判断是<=,否则最小元素的更新记录会出问题
如果写成if (x<min_order.top()),例如以下测试用例:
原来min_order存储了0,1,现pop了0,之后执行getMin会返回1,而不是0
提交结果
方法2:差值栈(★)
即不用第二个栈记录最小元素的出现顺序,用差值存储,即只用一个差值栈
差值栈存储的是元素x与当前最小值的差值x-min
push
当栈为空时,压入0(因为最小值和当前元素的值相等,即x==min,压入x-min==0)
当栈不为空时,正常压入x-min,如果x<min则更新min
pop
弹出栈顶元素,重点是min的更新问题
如果栈顶元素(x-min)大于0,说明x>min,min是不用更新的
如果栈顶元素(x-min)小于0,说明x-min的min是之前的最小值prev_min,而x则是当前栈的最小值min,设x-min=x-prev_min=min-prev_min,那就要将prev_min的值取出来,更新为当前栈的最小值
作差即可: min=min-(x-prev_min)=min-(min-prev_min)=prev_min
getMin
返回成员变量min即可
top
由于是差值栈,所以不能返回st.top()
栈顶存储的是x-min的值,但也不能直接返回x-min+min=st.top()+min
栈顶元素<0,说明栈顶元素值为x-prev_min=min-prev_min,则x==min,返回min即可
栈顶元素>=0,说明栈顶元素值为x-min,则返回st.top()+min即可
成员变量min和差值栈的类型
long long min;
stack<long long> st;使用int会可能溢出,因为st.push(x - min);的x - min可能会超出int的范围,例如INT_MAX-INT_MIN
正确代码:
class MinStack {
public:
MinStack() {}
void push(int x)
{
if (st.empty())
{
min = x;
st.push(0);//push(x-min)
return;
}
st.push(x - min);
if (x < min)
min = x;
}
void pop()
{
if (st.top() < 0)
min -= st.top();
st.pop();
}
int top()
{
if (st.top() >= 0)
return st.top() + min;
return min;
}
int getMin()
{
return min;
}
long long min;
stack<long long> st;
};提交结果
