php开发技术面试题及答案交流，php全栈面试题

今天小编为大家分享Windows系统下载、Windows系统教程、windows相关应用程序的文章，希望能够帮助到大家！

　　大家好，我是一名资深的操作系统优化师，今天我想和大家聊一下关于PHP面试题的一个问题。这个问题是关于如何使用两个普通栈实现一个特殊栈，要求其中的pop、push、min三个函数的操作复杂度都是O(1)，而且min函数需要获得当前栈的最小值。

　　开始的时候，我第一个想法是事先计算好当前最小值，并用一个变量来保存它。这样push和min函数就可以变成O(1)的操作了。但是遇到了一个问题，如果当前弹出的是最小值，那么就需要重新寻找当前元素的最小值，这样pop操作就不是O(1)了。

　　然后我又想到了一个方法，在一个栈中存储排好序的元素。这样push和pop操作就可以维护这个有序栈了。但是问题是，虽然min操作是O(1)，但是push和pop操作因为要维护这个有序栈，我怎么也想不到一个O(1)的方法。

　　当时我觉得肯定是在另一个栈中粗暴地缓存最小值信息，但是不知道是因为没吃饭还是怎么的，我的思维就僵住了。

　　后来我吃饭的时候，我突然想到了一个方法。我想到了用一个辅助栈来缓存每次栈的操作的最小值，这不就刚好解决了我们的问题嘛!这样每次pop操作的时候，两边一起弹出取出就可以了。因为辅助栈的栈顶元素就是当前栈中的最小值，而push操作只需要比较入栈元素和辅助栈栈顶元素的大小就可以了。这样push、pop、min函数都是O(1)的操作了。

　　以下是我用PHP实现的代码，通过数组来模拟堆栈：

　　```php

　　class Stack {

　　private $_arrData = array();

　　private $_arrMin = array();

　　private $_top = -1;

　　public function pop() {

　　if ($this->_top === -1) {

　　return false;

　　}

　　array_pop($this->_arrMin);

　　$this->_top--;

　　return array_pop($this->_arrData);

　　}

　　public function push($element) {

　　$element = intval($element);

　　if ($this->_top === -1) {

　　array_push($this->_arrData, $element);

　　array_push($this->_arrMin, $element);

　　$this->_top++;

　　return true;

　　}

　　$min = $this->_arrMin[$this->_top];

　　$currentMin = $element < $min ? $element : $min;

　　array_push($this->_arrMin, $currentMin);

　　array_push($this->_arrData, $element);

　　$this->_top++;

　　return true;

　　}

　　public function min() {

　　if ($this->_top === -1) {

　　return false;

　　}

　　return $this->_arrMin[$this->_top];

　　}

　　}

　　$obj = new Stack();

　　$obj->push(12);

　　$obj->push(56);

　　$obj->push(23);

　　$obj->push(89);

　　$obj->push(4);

　　var_dump($obj->min());

　　$obj->pop();

　　var_dump($obj->min());

　　$obj->push(8);

　　var_dump($obj->min());

　　```

　　输出结果为：

　　```

　　int(4)

　　int(12)

　　int(8)

　　```

wWw.Xtw.com.Cn系统网专业应用软件下载教程，免费windows10系统,win11,办公软件,OA办公系统,OA软件,办公自动化软件,开源系统,移动办公软件等信息，解决一体化的办公方案。