题干
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。
解题思路
首先本题有时间复杂度的限制，对于常规的栈来说，push和pop原本就是O(1)的操作，但是min却是O(n)的操作，所以我们需要考虑下如何记录最小元素，使用空间换时间的思路，我们可以提供一个辅助栈，用于存储每个push或pop操作之后栈中最小元素，将其存入辅助栈，这样辅助栈的栈顶就一直保存着当前时刻栈中的最小元素。
代码实现
<?php
class Stack
{
private $dataArray = [];
private $minArray = [];
function min()
{
if (count($this->minArray) > 0 && count($this->dataArray) > 0) {
return $this->minArray[0];
}
return null;
}
function pop()
{
array_shift($this->minArray);
return array_shift($this->dataArray);
}
function push($value)
{
array_unshift($this->dataArray, $value);
if (count($this->minArray) == 0 || $this->minArray[0] > $value) {
array_unshift($this->minArray, $value);
} else {
array_unshift($this->minArray, $this->minArray[0]);
}
}
}
$stack = new Stack();
$stack->push(3);
$stack->push(5);
$stack->push(2);
$stack->push(4);
$stack->push(1);
echo $stack->min();
$stack->pop();
echo $stack->min();
$stack->pop();
$stack->pop();
echo $stack->min();
