首页 > php教程 > php手册 > 用PHP解决的一个栈的面试题

用PHP解决的一个栈的面试题

WBOY
发布: 2016-06-06 20:20:42
原创
1456 人浏览过

这篇文章主要介绍了用PHP解决的一个栈的面试题,准备面试的高端PHP程序员可以看看,需要的朋友可以参考下

前言

遇到一道面试题,题目大概意思如下:

使用两个普通栈实现一个特殊栈,使得pop、push、min三个函数的都是复杂度为O(1)的操作,min函数是获得当前栈的最小值。

初步想法

1.要实现min函数为(1)操作,当时第一想法是事先需要算好当前最小值,于是会想到用一个值来保存当前栈中最小值元素,然后push和pop操作的时候维护这个值。这样min,push都是O(1)了,但pop可不是,如果当前弹出的是最小值,需要从新寻找当前元素的最小值,这个就不是o(1)了。

2.而且上面方法没有用到另外一个栈,于是又想到:在一个栈中存储排好序的元素,同样在push和pop操作中维护这个有序堆栈,如图:

但是这样的话min操作是O(1),但是push、pop操作因为要维护这个有序栈,怎么也想不到一个方法可以O(1)的复杂度。

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

正确解法

遇到问题解决不了,感觉心里很不爽,于是吃饭的时候又开始想怎么充分理由栈的特性,有效的缓存最小值信息,以便min操作使用。

栈操作最大的特性是只能操作栈顶元素,,想到那用一个辅助栈缓存每次栈操作时的最小值,不是刚刚好。这样每次pop操作的时候,两边一起弹出就可以;因为辅助栈的栈顶元素最当前栈中的最小值,push操作是也只需要比较入栈元素和辅助栈栈顶元素就可以。这样push、pop、min都都O(1)操作了。如图:

文字可能没说清楚,上代码,下面是PHP的实现,通过数组来模拟堆栈。

_top === -1){ return false; } array_pop($this->_arrMin); $this->_top--; return array_pop($this->_arrData); } /*** 入栈 * @param int $元素 * @返回布尔值*/ 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; } /*** 求当前栈空间的最小值 * @return bool|int*/ public function min(){ if ($this->_top === -1){ return false; } return $this->_arrMin[$this->_top]; } }

使用如下:

复制代码 代码如下:


$obj = new strack();
$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)

OK,满足要求。

你是否有其他更好方法实现,如果有,请告诉我^_^

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门推荐
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板