《剑指Offer》-30.包含min函数的栈

题干

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的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();