最小栈

怎样从“实现 MinStack: push 3,1,2,getMin=1; pop 弹出 2 后 getMin 仍为 1; 再 pop 弹出 1 后 getMin 回到 3。”推导出 栈 · 辅助栈，并证明每次状态变化都不会漏掉答案？

中心结论：双栈同步版:dataStack 存真实元素,minStack 每层压 min(x,当前 min),两栈等长同步 push/pop。

这道题是一个数据结构实现题。要求实现一个栈的类，实现 push()、pop()、top()、getMin()。

在本站主例中，实现 MinStack: push 3,1,2,getMin=1; pop 弹出 2 后 getMin 仍为 1; 再 pop 弹出 1 后 getMin 回到 3。

算法最终需要得到或观察：getMin=1; 第一次 pop(2) 后 min 仍为 1; 第二次 pop(1) 后 min 回到 3。

每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“栈与队列轨道”，明确答案需要观察什么。
2. 2状态只维护 dataStack、minStack(与 data 等长)、getMin 读 minStack 栈顶。
3. 3转移每一步按照 双栈同步版:dataStack 存真实元素,minStack 每层压 min(x,当前 min),两栈等长同步 push/pop。
4. 4收尾读取 getMin=1; 第一次 pop(2) 后 min 仍为 1; 第二次 pop(1) 后 min 回到 3。，并复核边界与复杂度。

入栈/入队的不是所有历史，而是未来仍需要的信息。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dataStack、minStack(与 data 等长)、getMin 读 minStack 栈顶。

双栈同步版:dataStack 存真实元素,minStack 每层压 min(x,当前 min),两栈等长同步 push/pop。

执行过程中持续维护：dataStack、minStack(与 data 等长)、getMin 读 minStack 栈顶。

正确性依赖以下不变量：dataStack 和 minStack 长度始终相同;minStack[i] 表示 dataStack[0..i] 的最小值;因此 minStack 栈顶永远是当前栈最小值。

面试时可以压缩为：我用两个栈。dataStack 存真实元素,minStack 存每一层对应的历史最小值。push 时压入 min(x, 当前 min),pop 时两个栈同步弹出,top 看 dataStack 栈顶,getMin 看 minStack 栈顶。四个操作 O(1),空间 O(n)。

落到当前题，执行机制可以压缩为：双栈同步版:dataStack 存真实元素,minStack 每层压 min(x,当前 min),两栈等长同步 push/pop。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入实现 MinStack: push 3,1,2,getMin=1; pop 弹出 2 后 getMin 仍为 1; 再 pop 弹出 1 后 getMin 回到 3。 因为：双栈同步版:dataStack 存真实元素,minStack 每层压 min(x,当前 min),两栈等长同步 push/pop。
2. 2dataStack + minStack 同步双栈双栈同步版:每层 minStack 存前缀最小。 因为：pop 后 min 从 minStack 栈顶 O(1) 恢复,无需扫描。
3. 3push(1) data=[3,1] mins=[3,1]dataStack 与 minStack 同时增加一层。 因为：mins[i] = min(data[0..i]); 栈顶即当前最小。
4. 4push(2) data=[3,1,2] mins=[3,1,1]dataStack 与 minStack 同时增加一层。 因为：mins[i] = min(data[0..i]); 栈顶即当前最小。
5. 5pop 弹出 2, getMin → 1两栈同步 pop; minStack 栈顶自动回到上一层最小。 因为：第一次 pop(2) 后 min 仍为 1,因为 1 还在栈里。
6. 6pop 弹出 1, getMin → 3两栈同步 pop; minStack 栈顶自动回到上一层最小。 因为：第一次 pop(2) 后 min 仍为 1,因为 1 还在栈里。
7. 7预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
8. 8收尾与复杂度getMin=1; 第一次 pop(2) 后 min 仍为 1; 第二次 pop(1) 后 min 回到 3。 因为：时间 O(1) 各操作 · 空间 O(n)。双栈同步版:dataStack 存真实元素,minStack 每层压 min(x,当前 min),两栈等长同步 push/pop。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// MinStack define
type MinStack struct {
	elements, min []int
	l             int
}

/** initialize your data structure here. */

// Constructor define
func Constructor() MinStack {
	return MinStack{make([]int, 0), make([]int, 0), 0}
}

// Push define
func (this *MinStack) Push(x int) {
	this.elements = append(this.elements, x)
	if this.l == 0 {
		this.min = append(this.min, x)
	} else {
		min := this.GetMin()
		if x < min {
			this.min = append(this.min, x)
		} else {
			this.min = append(this.min, min)
		}
	}
	this.l++
}

func (this *MinStack) Pop() {
	this.l--
	this.min = this.min[:this.l]
	this.elements = this.elements[:this.l]
}

func (this *MinStack) Top() int {
	return this.elements[this.l-1]
}

func (this *MinStack) GetMin() int {
	return this.min[this.l-1]
}

func main() {
    // 1. 主例
    //    输入：mode="min-stack", ops=["push 3","push 1","push 2","getMin","pop","pop"]
    //    期望：getMin=1; 第一次 pop(2) 后 min 仍为 1; 第二次 pop(1) 后 min 回到 3。
    //
    // 2. 失败 / 未命中
    //    检查：pop 数据栈时忘记同步 pop minStack;误说「pop 一次后 min 自动回到 3」。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC20 有效括号；LC232 栈实现队列
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意实现 MinStack: push 3,1,2,getMin=1; pop 弹出 2 后 getMin 仍为 1; 再 pop 弹出 1 后 getMin 回到 3。
2. 2重复每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。
3. 3优化双栈同步版:dataStack 存真实元素,minStack 每层压 min(x,当前 min),两栈等长同步 push/pop。
4. 4证明dataStack 和 minStack 长度始终相同;minStack[i] 表示 dataStack[0..i] 的最小值;因此 minStack 栈顶永远是当前栈最小值。
5. 5复杂度时间 O(1) 各操作，空间 O(n)