从MODIS像素到火灾边界：拆解GlobFire v2数据集的生成算法与GEE应用
2026/6/12 14:23:00
一、题目描述
设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类：
| 操作 | 说明 |
|---|---|
| MinStack() | 初始化堆栈对象 |
| void push(int value) | 将元素 value 推入堆栈 |
| void pop() | 删除堆栈顶部的元素 |
| int top() | 获取堆栈顶部的元素 |
| int getMin() | 获取堆栈中的最小元素 |
示例：
输入： ["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); // 栈: [-2] minStack.push(0); // 栈: [-2, 0] minStack.push(-3); // 栈: [-2, 0, -3] minStack.getMin(); // 返回 -3 minStack.pop(); // 栈: [-2, 0] minStack.top(); // 返回 0 minStack.getMin(); // 返回 -2提示：
- -2^31 <= val <= 2^31 - 1
- pop、top 和 getMin 操作总是在非空栈上调用
- push, pop, top, getMin 最多被调用 3 * 10^4 次
二、解题思路总览
这道题的核心难点：如何在 O(1) 时间内获取最小元素？
普通栈只能 O(1) 获取栈顶元素，但获取最小值需要遍历整个栈，是 O(n)。
关键洞察：如果我们能记录"每个位置之前的最小值"，那么栈顶的最小值就是"当前元素入栈时的最小值"。
核心思路：
| 步骤 | 思路 | 说明 |
|---|---|---|
| 1 | 使用辅助栈 | 一个栈存数据，一个栈存当前最小值 |
| 2 | 同步维护 | 每次 push/pop，两个栈同时操作 |
| 3 | O(1) 获取最小 | 直接从辅助栈栈顶取最小值 |
为什么用双栈？
| 对比 | 不用辅助栈 | 用辅助栈 |
|---|---|---|
| getMin 复杂度 | O(n) -遍历栈 | O(1) - 直接取 |
| push/pop 复杂度 | O(1) | O(1) |
| 空间复杂度 | O(n) | O(n) |
| 实现难度 | 简单 | 简单 |
三、完整代码
方法一：双栈法（辅助栈）
classMinStack{public:MinStack(){// 初始化辅助栈，预先放入一个极大值minSt.push(INT_MAX);}voidpush(intvalue){st.push(value);// 辅助栈：每次push时存入当前最小值minSt.push(min(minSt.top(),value));}voidpop(){st.pop();minSt.pop();}inttop(){returnst.top();}intgetMin(){returnminSt.top();}private:stack<int>st;// 数据栈stack<int>minSt;// 辅助栈，栈顶永远存当前最小值};四、其他解法
方法二：单栈 + 结构体（存储差值）
classMinStack{public:MinStack(){}voidpush(intvalue){if(st.empty()){// 第一个元素，最小值就是它自己st.push({value,value});}else{longlongdiff=(longlong)value-st.top().second;st.push({value,st.top().second});// 用差值存储，节省空间// 如果diff <= 0，说明value更小，更新最小值if(diff<=0){st.top().second=value;}}}voidpop(){st.pop();}inttop(){returnst.top().first;}intgetMin(){returnst.top().second;}private:stack<pair<int,int>>st;// {实际值, 当前最小值}};注意：这里用pair<value, currentMin>存储，getMin 时直接取 second即可。
方法三：单栈存差值法（空间优化，面试技巧）
classMinStack{public:MinStack(){}voidpush(intvalue){if(st.empty()){st.push(value);minVal=value;}else{// 如果value更小，先存差值（负数），更新minValif(value<minVal){st.push((longlong)value-minVal);minVal=value;}else{// value >= minVal，存正差值st.push(value-minVal);}}}voidpop(){longlongtop=st.top();st.pop();if(top<0){// top< 0 说明栈顶是更新minVal时存入的差值// 恢复之前的最小值minVal=minVal-top;}if(st.empty()){minVal=0;// 或者不设置，因为栈空了}}inttop(){longlongtop=st.top();if(top<0){// 栈顶是差值，说明当前最小值就是栈顶元素本身return(int)top;}else{// 栈顶是正差值，实际值 = minVal + 差值return(int)(minVal+top);}}intgetMin(){return(int)minVal;}private:stack<longlong>st;// 存差值longlongminVal=LLONG_MAX;// 当前最小值};技巧说明：利用差值正负来标记是否更新了最小值。适合面试时展示思维深度。
方法四：链表实现栈（纯天然O(1)最小值）
classMinStack{public:MinStack(){}voidpush(intvalue){intnewMin=value;if(head){newMin=min(head->minVal,value);}// 在链表头插入新节点ListNode*node=newListNode(value,newMin,head);head=node;}voidpop(){if(head){ListNode*temp=head;head=head->next;deletetemp;}}inttop(){returnhead->val;}intgetMin(){returnhead->minVal;}private:structListNode{intval;intminVal;// 到此节点为止的最小值ListNode*next;ListNode(intv,intm,ListNode*n):val(v),minVal(m),next(n){}};ListNode*head=nullptr;// 栈顶就是链表头};思路：每个链表节点自带"到当前位置的最小值"，getMin 直接取栈顶节点的 minVal。
五、算法流程图
以方法一为例，展示push(-2)→push(0)→push(-3)→pop()的过程：
初始状态： ┌─────────────┬─────────────┐ │ 数据栈 │ 辅助栈 │ │ [空] │ [空] │ └─────────────┴─────────────┘ Step 1: push(-2) ┌─────────────┬─────────────┐ │ 数据栈 │ 辅助栈 │ │ [-2] │ [-2] │ └─────────────┴─────────────┘ minSt.top() = -2 ← 当前最小值 Step 2: push(0) ┌─────────────┬─────────────┐ │ 数据栈 │ 辅助栈 │ │ [-2, 0] │ [-2, -2] │ └─────────────┴─────────────┘ minSt.top() = -2 ← 当前最小值（-2< 0） Step 3: push(-3) ┌─────────────┬─────────────┐ │ 数据栈 │ 辅助栈 │ │ [-2,0,-3] │ [-2,-2,-3] │ └─────────────┴─────────────┘ minSt.top() = -3 ← 当前最小值（更新！） Step 4: pop() ┌─────────────┬─────────────┐ │ 数据栈 │ 辅助栈 │ │ [-2, 0] │ [-2, -2] │ └─────────────┴─────────────┘ minSt.top() = -2 ← 自动恢复之前的最小值六、逐行解析（方法一）
MinStack(){minSt.push(INT_MAX);}初始化：辅助栈预先放入极大值，确保第一次 push 时 min 取值正确。
voidpush(intvalue){st.push(value);minSt.push(min(minSt.top(),value));}同步 push：数据入数据栈，辅助栈存入"当前最小值"（原最小值与新入值的较小者）。
voidpop(){st.pop();minSt.pop();}同步 pop：两个栈同时弹出栈顶，保持同步。
intgetMin(){returnminSt.top();}O(1) 获取最小值：直接返回辅助栈栈顶，不需要遍历。
七、复杂度分析
各方法复杂度对比
| 方法 | push | pop | top | getMin | 空间 | 说明 |
|---|---|---|---|---|---|---|
| 方法一：双栈 | O(1) | O(1) | O(1) | O(1) | O(n) | 标准解法 |
| 方法二：结构体栈 | O(1) | O(1) | O(1) | O(1) | O(n) | 代码清晰 |
| 方法三：差值法 | O(1) | O(1) | O(1) | O(1) | O(n) | 面试技巧，需处理溢出 |
| 方法四：链表 | O(1) | O(1) | O(1) | O(1) | O(n) | 思路新颖，需手动管理内存 |
核心：所有方法都保证 getMin 是 O(1)！
方法一详细复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| push | O(1) | O(1) | 一次入栈，一次取min，一次入栈 |
| pop | O(1) | O(1) | 两次出栈 |
| top | O(1) | O(1) | 直接取栈顶 |
| getMin | O(1) | O(1) | 直接取辅助栈栈顶 |
最坏空间复杂度：O(n)
- 两个栈最多各存 n 个元素
- 实际辅助栈和数据栈元素数量相同
八、面试追问 FAQ
| 问题 | 回答要点 |
|---|---|
| Q1: 为什么不用一个变量存最小值？ | 因为 pop 时不知道上一个最小值是多少。需要历史记录，栈天然提供这个能力。 |
| Q2: 辅助栈能不能更省空间？ | 可以用方法三（差值法）或方法二（结构体），但会增加代码复杂度。空间换可读性 vs 可读性换空间，需要权衡。 |
| Q3: 如果要支持 O(1) 求最大值怎么办？ | 思路相同，再加一个 maxSt 辅助栈。或者用结构体同时存 {value, currentMin, currentMax}。 |
| Q4: 面试时推荐哪种方法？ | 首选方法一（双栈），代码清晰不易出错。如果面试官问空间优化，再引出方法三。 |
| Q5: 差值法有什么陷阱？ | 注意 long long 溢出。当 value 是 INT_MIN，差值计算可能溢出。另外 top() 的实现也容易出错。 |
| Q6: 能不用额外空间吗？ | 目前没有已知方法能在 O(1) getMin 下实现 O(1) 空间，这是该题的数学本质。 |
九、相关题目
| 题号 | 题目 | 难度 | 关联点 |
|---|---|---|---|
| 155 | 最小栈 | 中等 | 本题 |
| 225 | 用队列实现栈 | 简单 | 数据结构设计 |
| 232 | 用栈实现队列 | 简单 | 数据结构设计 |
| 716 | 最大栈 | 困难 | 扩展到最大值 |
| 剑指 Offer 30 | 包含min函数的栈 | 简单 | 本题变种 |
推荐刷题顺序：
- 本题（155.最小栈）→ 基础
- 225/232（用队列实现栈/用栈实现队列）→ 数据结构设计思想
- 716（最大栈）→ 扩展到最大值
十、总结
| 维度 | 内容 |
|---|---|
| 考察知识点 | 栈的设计、辅助数据结构 |
| 难度 | 中等 |
| 核心思维 | 用空间换时间，用辅助栈记录历史最小值 |
| 关键技巧 | push/pop 时同步维护辅助栈 |
| 推荐解法 | 方法一（双栈）- 标准、清晰、可靠 |
| 面试加分 | 方法三（差值法）- 展示思维深度 |
一句话总结：最小栈的核心是用一个辅助栈"同步记录每个位置的当前最小值"，这样 getMin 永远是 O(1)。空间换时间，是算法设计中永恒的trade-off。