最小栈的实现
2019-12-13 本文已影响0人
吕艳凯
题目
实现一个栈，该栈带有出栈（pop）、入栈（push）、取最小元素（getMin）3个方法。要保证这3个方法的时间复杂度都是O(1)。
image.png
详细的解法步骤如下：
-
设原有的栈叫作栈A，此时创建一个额外的“备胎”栈B，用于辅助栈A。
image.png
-
当第1个元素进入栈A时，让新元素也进入栈B。这个唯一的元素是栈A的当前最小值。
image.png
-
之后，每当新元素进入栈A时，比较新元素和栈A当前最小值的大小，如果小于栈A当前最小值，则让新元素进入栈B，此时栈B的栈顶元素就是栈A当前最小值。
image.png
-
每当栈A有元素出栈时，如果出栈元素是栈A当前最小值，则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的，是栈A当中原本第2小的元素，代替刚才的出栈元素成为栈A的当前最小值。（备胎转正。）
image.png
- 当调用getMin方法时，返回栈B的栈顶所存储的值，这也是栈A的最小值。
具体代码如下：
class Code{
public $stack = array();
public $minStack = array();
function stackPush($data){
array_push($this->stack, $data);
if(!$this->minStack || end($this->minStack) > $data){
array_push($this->minStack, $data);
}
}
function stackPop(){
$stackTop = array_pop($this->stack);
if($stackTop == end($this->minStack)){
array_pop($this->minStack);
}
return $stackTop;
}
function getMin(){
if(!$this->minStack){
var_dump("栈为空");
}
return end($this->minStack);
}
}
$obj = new Code();
$obj->stackPush(9);
$obj->stackPush(4);
$obj->stackPush(7);
$obj->stackPush(3);
var_dump($obj->stack);
var_dump($obj->getMin());
$obj->stackPop();
var_dump($obj->stack);
var_dump($obj->getMin());
输出结果：
image.png
