HHot 100C++ 图解

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 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

思路

空间O(n)

思路

要求 getMin 也是 O(1)。做法:再开一个「最小值栈」,每次 push 时把「压入后的当前最小值」同步压进去,pop 时一起弹。

两栈高度始终相同,所以不必比较值是否相等(最小值重复出现也正确)。

空间优化

辅助栈只在 x <= 当前最小值时才压入,pop 时同步弹出。

图解

-2 0 0 1 -3 2 -2 0 0 1 -3 2
左边是正常栈,右边是「辅助最小栈」:每次压栈时,若新值 ≤ 当前最小值则同步压入。出栈时若弹出的值等于最小栈顶,则最小栈也弹。存过的「当时最小值」随时可查。

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/12_stack.cpp22 行
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_;
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q155_min_stack17 行
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);

↑↓ 选择↵ 打开/ 随时唤起