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

2020-03-22 19:04:23

字体：大中小

来源：转载

供稿：网友

遇到一道面试题，题目大概意思如下：使用两个普通栈实现一个特殊栈，使得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的实现，通过数组来模拟堆栈。 * 使用一个辅助栈，O(1)复杂度求出栈中的最小数 * @hack 类中通过数组来模拟堆栈 * @author laiwenhuihtml' target='_blank'>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，满足要求。你是否有其他更好方法实现，如果有，请告诉我^_^PHP教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。

上一篇：ThinkPHP实现跨模块调用操作方法概述

下一篇：PHP面试总结