当前位置：首页 > backend >正文

LeetCode-栈-最小栈

backend 2025/7/28 0:12:17

LeetCode-栈-最小栈

✏️ 关于专栏：专栏用于记录 prepare for the coding test。

文章目录

LeetCode-栈-最小栈
- 📝 最小栈
- - 🎯题目描述
  - 🔍 输入输出示例
  - 🧩题目提示
  - 🧪AC
- 🌟 总结

📝 最小栈

🎯题目描述

设计一个支持 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]

示例 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.

🧩题目提示

$2^{31} <= val <= 2^{31} - 1$
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

🧪AC

我们可以将本题视为：

对一个数组 nums 模拟栈的操作，在这个「栈」中动态地添加/删除元素，并且实时维护最小值。

为了做到在 O(1) 时间内获取最小值，除了将元素本身加入栈，我们还可以一并保存该元素对应的“前缀最小值”。

我们用一个栈 st 来保存如下结构：

pair<int, int>  // {val, 当前为止的最小值}

其中：

val 是当前入栈的值；
第二个元素表示到当前为止，整个栈中的最小值。

添加元素（push）

假设当前栈的大小为 n，我们将新元素 val 入栈时：

如果栈是空的：最小值就是 val 本身。
否则：比较 val 与栈顶元素的最小值，选择较小者作为新的前缀最小值。

int curMin = st.empty() ? val : min(val, st.top().second);
st.push({val, curMin});

删除元素（pop）

直接弹出栈顶即可，前缀最小值随之更新（由栈自动维护）。

st.pop();

获取栈顶元素（top）

return st.top().first;

获取当前最小值（getMin）

return st.top().second;

class MinStack {stack<int> x_stack;stack<int> min_stack;
public:MinStack() {min_stack.push(INT_MAX);}void push(int x) {x_stack.push(x);min_stack.push(min(min_stack.top(), x));}void pop() {x_stack.pop();min_stack.pop();}int top() {return x_stack.top();}int getMin() {return min_stack.top();}
};