用PHP解决的一个栈的面试题
2015-01-24信息快讯网
这篇文章主要介绍了用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的实现,通过数组来模拟堆栈。
<?php /** * 使用一个辅助栈,O(1)复杂度求出栈中的最小数 * @hack 类中通过数组来模拟堆栈 * * @author laiwenhui */ class strack{ /** * 数据栈,存储栈数据; * * @var array */ private $_arrData = array(); /** * 辅助栈,存储数据组栈中每层的最下值信息; * * @var array */ private $_arrMin = array(); /** * 栈顶所在单元 * * @var int */ private $_top=-1; /** * 出栈 * @return bool|int */ public function pop(){ if ($this->_top === -1){ return false; } array_pop($this->_arrMin); $this->_top--; return array_pop($this->_arrData); } /** * 入栈 * @param int $element * @return bool */ 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,满足要求。
你是否有其他更好方法实现,如果有,请告诉我^_^
分享最受欢迎的5款PHP框架
PHP比你想象的好得多
简单说说PHP优化那些事(经验分享)
几个实用的PHP内置函数使用指南
简单谈谈php中ob_flush和flush的区别
ThinkPHP提交表单时默认自动转义的解决方法
ThinkPHP控制器里javascript代码不能执行的解决方法
PHP判断一个gif图片是否为动态图片的方法
一个比较不错的PHP日历类分享
php集成环境xampp中apache无法启动问题解决方案
一个经典的PHP文件上传类分享
一个经典的PHP验证码类分享
一个经典实用的PHP图像处理类分享
PHP采用get获取url汉字出现乱码的解决方法
PHP使用json_encode函数时不转义中文的解决方法
PHP中提问频率最高的11个面试题和答案
几道坑人的PHP面试题 试试看看你会不会也中招
PHP中设置一个严格30分钟过期Session面试题的4种答案
PHP反射使用实例和PHP反射API的中文说明
函数中使用require_once问题深入探讨 优雅的配置文件定义方法推荐
PHP中遇到BOM、<feff>编码导致json_decode函数无法解析问题
php foreach正序倒序输出示例代码
浅析ThinkPHP的模板输出功能
ThinkPHP中的系统常量和预定义常量集合
ThinkPHP实现多数据库连接的解决方法
ThinkPHP框架实现session跨域问题的解决方法
ThinkPHP的cookie和session冲突造成Cookie不能使用的解决方法
编译PHP报错configure error Cannot find libmysqlclient under usr的解决方法
ThinkPHP采用GET方式获取中文参数查询无结果的解决方法
分享一个php 的异常处理程序
PHP封装的一个支持HTML、JS、PHP重定向的多功能跳转函数
一个严格的PHP Session会话超时时间设置方法
使用PHP破解防盗链图片的一个简单方法
php 批量添加多行文本框textarea一行一个
php牛逼的面试题分享
关于访问控制的一首PHP面试题(对属性或方法的访问控制)