155. 最小栈
一句话套路辅助最小栈同步压入/弹出
题目描述
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int value)将元素value推入堆栈。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(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示:
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
思路
空间
O(n)思路
要求 getMin 也是 O(1)。做法:再开一个「最小值栈」,每次 push 时把「压入后的当前最小值」同步压进去,pop 时一起弹。
两栈高度始终相同,所以不必比较值是否相等(最小值重复出现也正确)。
空间优化
辅助栈只在 x <= 当前最小值时才压入,pop 时同步弹出。
图解
左边是正常栈,右边是「辅助最小栈」:每次压栈时,若新值 ≤ 当前最小值则同步压入。出栈时若弹出的值等于最小栈顶,则最小栈也弹。存过的「当时最小值」随时可查。
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0155 {
class MinStack {
public:
void push(int val) {
st_.push(val);
// 关键:压的是「val 与当前最小值里的较小者」,min_ 栈顶永远是 st_ 全体的最小值
min_.push(min_.empty() ? val : min(val, min_.top()));
}
void pop() {
st_.pop();
min_.pop();
}
int top() const { return st_.top(); }
int getMin() const { return min_.top(); }
private:
stack<int> st_;
stack<int> min_;
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0155::MinStack st;
st.push(-2);
st.push(0);
st.push(-3);
CHECK_EQ(st.getMin(), -3);
st.pop();
CHECK_EQ(st.top(), 0);
CHECK_EQ(st.getMin(), -2);
// 重复最小值:弹掉一个 2 之后,最小值仍是 2
lc0155::MinStack d;
d.push(2);
d.push(2);
d.push(1);
d.pop();
CHECK_EQ(d.getMin(), 2);
d.pop();
CHECK_EQ(d.getMin(), 2);