用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 $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 _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];
  }
}
使用如下：
[U]复制代码[/U] 代码如下:
$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());
输出为：
[U]复制代码[/U] 代码如下:
int(4)
int(12)
int(8)
OK，满足要求。
你是否有其他更好方法实现，如果有，请告诉我^_^
            
            
您可能感兴趣的文章:

php array_pop()数组函数将数组最后一个单元弹出（出栈）

php array_push()数组函数:将一个或多个单元压入数组的末尾（入栈）

php数组函数序列之array_push() 数组尾部添加一个或多个元素（入栈），返回新长度。

PHP中使用数组实现堆栈数据结构的代码

关于PHP堆栈与列队的学习

php线性表的入栈与出栈实例分析

基于PHP实现栈数据结构和括号匹配算法示例

PHP使用栈解决约瑟夫环问题算法示例

PHP基于堆栈实现的高级计算器功能示例

PHP栈的定义、入栈出栈方法及基于堆栈实现的计算器完整实例

PHP实现基于栈的后缀表达式求值功能