hot100 最小栈(155)

本题采用双栈同步映射算法又称“辅助栈最小状态克隆法”解决栈结构中常数时间检索最小元素的问题。其核心本质是将全局最小值的动态追踪转化为与数据栈严格同频的增量历史快照利用空间换时间策略消除线性扫描开销。当前提供的源码实现了在所有核心操作push、pop、top、getMin均为时间复杂度 O(1) 和额外空间复杂度 O(n) 条件下的全局状态锁定最终走向是精准维护栈内任意生存周期下的即时最小元素。一、 问题本质与数据模型对于标准的后进先出LIFO栈结构元素的迁入与迁出具有严格的单向时序。题目要求的特殊属性是在常数时间内输出栈内当前的全局最小值。如果仅在外部维护一个单一的min变量当发生push操作时可以做到常数级更新但一旦发生pop操作且弹出的刚好是这个最小值栈将丢失之前次小值的历史上下文必须被迫通过全盘线性遍历重新寻找最小元素这会导致时间复杂度退化至 O(n)。为了破除这种历史数据丢失的物理困局算法引入了“双栈时序对齐模型”。通过在底层并行构建两个线性容器一个作为标准数据栈data负责原始元素的存储与常规检索另一个作为辅助最小栈min负责同步克隆在当前栈深下的历史最小值状态。在任意物理时刻辅助栈的栈顶元素都精确映射了数据栈中现存全体元素的局部极小值。由此通过空间层面的状态冗余彻底消除了时间层面的回溯代价。二、 算法演进对比在实现最小栈的设计方案中辅助栈同步法在操作复杂度的均衡性上达到了最优极限解法名称时间复杂度 (getMin)空间复杂度核心原理物理瓶颈 / 缺陷单数据栈线性扫描O(n)O(1)仅维护标准栈调用 getMin 时通过迭代器遍历全栈寻优时间复杂度未达标高频检索时算力开销随数据深度线性激增辅助栈同步映射当前解法O(1)O(n)数据栈与最小栈严格同频最小栈顶实时锁定当前历史最小值产生了完全一比一的空间冗余内存开销加倍单栈差值存储法O(1)O(1)栈中仅存储当前值与最小值的差值动态还原原始数值与极值不需要额外栈空间但数值涉及频繁做差在数据边缘如接近整型最大/最小值存在整型溢出风险三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于push函数内的容器状态判定与极值归纳其内部决策分支证明如下1. 初始准入分支if (min.isEmpty())执行min.add(val);物理意义当最小栈为空时意味着数据栈迎来了生命周期的首个物理元素。该元素不存在任何外部竞争对手天然成为当前状态下的全局极小值直接写入最小栈底。2. 状态增量演进分支else 判定执行min.add(Math.min(val, min.getLast()));数学证明假设当前插入元素为val执行前一历史状态的最小值为min_old。新状态下的全体元素集合为新旧集合的并集。根据数学归纳新集合的极小值必然是旧极小值与新加入值之中的较小者即Math.min(val, min_old)。通过将计算结果压入辅助栈顶证明了新状态快照的数学完备性。3. 同步出栈控制pop()执行data.removeLast(); min.removeLast();物理意义由于入栈时维持了绝对的一比一数量对齐出栈时必须无条件同步弹出两个栈的顶部元素。这确保了在物理空间缩减后最小栈的下一任新栈顶依然能够精准对齐数据栈剩余元素历史截面上的极小值。四、 算法执行状态机步进示例以示例 1 的操作序列为例展示双栈状态机在时间流中的演进过程注物理容器采用标准线性表尾部对齐模型步骤调用的核心方法压入/弹出数值数据栈物理状态 (data)最小栈物理状态 (min)返回值与全局状态说明初始MinStack()-[ ][ ]状态初始化双栈为空1push(-2)-2[-2][-2]最小栈空直接同步压入 -22push(0)0[-2, 0][-2, -2]min(-2, 0) -2最小栈克隆前状态值3push(-3)-3[-2, 0, -3][-2, -2, -3]min(-2, -3) -3更新最新历史极值4getMin()-[-2, 0, -3][-2, -2, -3]O(1) 获取最小栈顶精准返回 -35pop()-[-2, 0][-2, -2]同步物理弹出栈顶成功回溯至步骤 2 的状态快照6top()-[-2, 0][-2, -2]获取数据栈顶返回 07getMin()-[-2, 0][-2, -2]O(1) 获取当前最小栈顶精准返回 -2五、 源码实现import java.util.ArrayList; import java.util.List; class MinStack { // 数据栈承载标准的物理数据 private ListInteger data; // 最小辅助栈负责同步克隆每个状态截面下的全局最小值 private ListInteger min; /** 初始化堆栈对象 */ public MinStack() { data new ArrayList(); min new ArrayList(); } /** 将元素 value 推入堆栈 */ public void push(int val) { // 数据栈无条件接收新元素 data.add(val); // 条件控制若最小栈为空说明为首个元素直接作为当前最小值入栈 if (min.isEmpty()) { min.add(val); } else { // 状态归纳取当前新元素与历史极小值当前最小栈顶的较小者压入最小栈 min.add(Math.min(val, min.getLast())); } } /** 删除堆栈顶部的元素 */ public void pop() { // 核心同步控制利用 SequencedCollections 特性同步切除两个线性表的尾部元素 data.removeLast(); min.removeLast(); } /** 获取堆栈顶部的元素 */ public int top() { // 直接返回数据栈的尾部对应标准栈顶 return data.getLast(); } /** 获取堆栈中的最小元素 */ public int getMin() { // 常数阶响应直接读取最小栈的尾部元素该值即为当前历史状态下的绝对极小值 return min.getLast(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj new MinStack(); * obj.push(val); * obj.pop(); * int param_3 obj.top(); * int param_4 obj.getMin(); */六、 复杂度分析1. 时间复杂度O(1)分析算法将复杂的全栈极值搜索平摊到了每一次的数据迁入过程中。在push、pop、top和getMin操作中全部底层的调用逻辑均依托于基于动态数组实现的线性表尾部操作如add、removeLast、getLast。这些底层的指针位移、内存赋值与单次数学比较判定均属于原子级操作不依赖于栈内现存的元素总量 n。结论所有对外公开的方法均实现了严格的常数阶 O(1) 运行效率完美满足题目设计的极致时间约束。2. 空间复杂度O(n)分析算法为了在时间层面达到常数级响应在物理空间上做出了对等的牺牲。引入了额外的辅助容器min。在任意物理状态下辅助栈内的节点数量与标准数据栈data内的节点数量保持绝对的 1:1 同步线性增长。若栈内当前并发积压了 n 个元素整体内存开销呈 2n 线性展布。结论没有申请任何多维或非线性的外部复杂数据结构额外物理空间开销随元素总量呈线性正比空间复杂度定性为 O(n)。