最小栈是在普通栈基础上支持o(1)获取最小值的数据结构，通过主栈存元素、辅助栈同步存历史最小值实现；push时x
什么是“最小栈”
最小栈是指在实现普通栈（后进先出）功能的基础上，能以 O(1) 时间复杂度获取当前栈中元素的最小值。它不是调用内置 min() 函数，而是在入栈、出栈过程中动态维护最小值信息。
核心思路：用辅助栈同步记录最小值
主流解法是使用两个栈：
– 主栈（stack）：存所有入栈元素，负责 push/pop 操作；
– 辅助栈（minStack）：只存“历史最小值”，栈顶始终是当前主栈的最小值。
关键规则：
- push(x) 时，若
minStack为空，或x top()，则也把 x 压入minStack - pop() 时，若主栈弹出的元素等于
minStack->top()，则minStack也要同步 pop - getMin() 直接返回
minStack->top()，无需遍历
PHP 实现代码（类封装）
// 支持重复元素，使用 SplStack（PHP 标准栈）
class MinStack {
private $stack;
private $minStack;
public function __construct() {
$this->stack = new SplStack();
$this->minStack = new SplStack();
}
public function push($x) {
$this->stack->push($x);
if ($this->minStack->isEmpty() || $x <= $this->minStack->top()) {
$this->minStack->push($x);
}
}
public function pop() {
if ($this->stack->isEmpty()) return;
$val = $this->stack->pop();
if (!$this->minStack->isEmpty() && $val === $this->minStack->top()) {
$this->minStack->pop();
}
}
public function top() {
return $this->stack->isEmpty() ? null : $this->stack->top();
}
public function getMin() {
return $this->minStack->isEmpty() ? null : $this->minStack->top();
}
}
用法示例：
立即学习“PHP免费学习笔记（深入）”；
$minStack = new MinStack(); $minStack->push(-2); $minStack->push(0); $minStack->push(-3); echo $minStack->getMin(); // -3 $minStack->pop(); echo $minStack->top(); // 0 echo $minStack->getMin(); // -2
注意事项与常见误区
– 必须用 而非 <code> 入辅助栈：否则遇到重复最小值（如 push(0), push(0)）时，第二次 pop 会误删 minStack 中唯一记录，导致 getMin 错误<br>
– 注意类型严格比较（<code>===），避免 PHP 自动类型转换引发 bug（比如数字 0 和字符串 "0"）
– 不依赖全局变量或静态属性，确保多实例独立运行
– 空栈调用 top()/getMin() 应有安全返回（如 null），避免 Notice 报错
