用PHP解决的一堆面试问题

序

遇到了面授考试，题目大概意思如下：

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

初步想法

1.要将min函数实现为(1)运算，当时的第一个想法是提前计算当前的最小值，所以我想到了用一个值保存当前堆栈中的最小值元素，然后在push和pop操作期间保持这个值。这样，min和push都是O(1)，而pop不是。如果目前弹出最小值，需要重新寻找当前元素的最小值，所以这不是o(1)。

2.此外，上面的方法没有使用另一个堆栈，因此想到有序元素存储在一个堆栈中，并且有序堆栈也在推送和弹出操作中维护，如图所示：

然而，在这种情况下，min操作是O(1)，但是push和pop操作不能想到具有O(1)复杂性的方法，因为它们想要维护这个有序堆栈。

当时觉得一定是把最小的信息缓存在了另一个栈里，但不知道是因为没吃饭还是什么，脑子就僵住了。

正确的解决方案

遇到解决不了的问题，我觉得很苦恼，所以吃饭的时候，我开始思考如何充分说明栈的特性，有效缓存最小的信息，让它可以被min操作使用。

栈操作最大的特点是只能操作栈顶元素。使用辅助堆栈来缓存每个堆栈操作的最小值是不正确的。这样，每次操作pop时，双方都能一起弹出；因为辅助堆栈的堆栈顶部元素是当前堆栈中的最小值，所以推送操作只需要将堆栈入口元素与辅助堆栈的堆栈顶部元素进行比较。这样，推送、弹出和最小都是O(1)操作的。图片：

文本可能不清楚。下面是PHP的实现，它通过数组模拟堆栈。

？Php/** *使用一个辅助栈，O(1)复杂度计算栈中的最小数* @hack类模拟栈* * @作者赖文慧*/Class Strack {/* * * *数据通过数组栈，并存储栈数据；* * @ var array */private $ _ arrData=array()；/* * *辅助栈，存储数据组栈中各层的最低值信息；* * @ var array */private $ _ arrMin=array()；/* * *栈顶所在的单元* * @ var int */private $ _ top=-1；/* * * stack * @ return bool | int */public function pop(){ if($ this-_ top==-1){ return false；} array _ pop($ this-_ arrMin)；$ this-_ top-；返回array _ pop($ this-_ arrData)；}/* * * Stack * @ param int $ element * @ return bool */public function push($ element){ $ element=int val($ element)；//如果栈为空，直接输入栈If($ this-_ top===-1){ array _ push($ this-_ arr data，$ element)；array_push($this-_arrMin，$ element)；$ this-_ top；返回真；}//不为空，判断堆叠的值是否比最小堆叠顶小$ min=$ this-_ arrMin[$ this-_ top]；//比较并找出最小值$currentMin=$element $min？$元素： $ min//将当前栈中的最小值推入栈数组_ push ($ this-_ arrmin，$ current min)；//数据栈array _ push ($ this-_ arrdata，$ element)；$ this-_ top；返回真；}/* * *查找当前堆栈空间的最小值* @ return bool | int */public function min(){ if($ this-_ top==-1){ return false；}返回$ this-_ Arrmin[$ this-_ top]；}}的用法如下：复制代码如下： $ obj=news ack()；$ 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)。

好的，符合要求。

你还有其他更好的方法吗？如果是，请告诉我。