用PHP解決的一個棧的面試題

更新時間：2014年07月02日 11:39:23 投稿：junjie

這篇文章主要介紹了用PHP解決的一個棧的面試題,準(zhǔn)備面試的高端PHP程序員可以看看,需要的朋友可以參考下

前言

遇到一道面試題，題目大概意思如下：

使用兩個普通棧實(shí)現(xiàn)一個特殊棧，使得pop、push、min三個函數(shù)的都是復(fù)雜度為O(1)的操作，min函數(shù)是獲得當(dāng)前棧的最小值。

初步想法

1.要實(shí)現(xiàn)min函數(shù)為(1)操作，當(dāng)時第一想法是事先需要算好當(dāng)前最小值,于是會想到用一個值來保存當(dāng)前棧中最小值元素，然后push和pop操作的時候維護(hù)這個值。這樣min,push都是O(1)了，但pop可不是，如果當(dāng)前彈出的是最小值，需要從新尋找當(dāng)前元素的最小值，這個就不是o(1)了。

2.而且上面方法沒有用到另外一個棧，于是又想到：在一個棧中存儲排好序的元素，同樣在push和pop操作中維護(hù)這個有序堆棧，如圖：

但是這樣的話min操作是O(1)，但是push、pop操作因?yàn)橐S護(hù)這個有序棧，怎么也想不到一個方法可以O(shè)(1)的復(fù)雜度。

當(dāng)時覺得肯定是在另一個棧中緩存最小值信息，但是不知道是因?yàn)闆]吃飯還是怎么地，思維就此僵住了。

正確解法

遇到問題解決不了，感覺心里很不爽，于是吃飯的時候又開始想怎么充分理由棧的特性，有效的緩存最小值信息，以便min操作使用。

棧操作最大的特性是只能操作棧頂元素，想到那用一個輔助棧緩存每次棧操作時的最小值，不是剛剛好。這樣每次pop操作的時候，兩邊一起彈出就可以；因?yàn)檩o助棧的棧頂元素最當(dāng)前棧中的最小值，push操作是也只需要比較入棧元素和輔助棧棧頂元素就可以。這樣push、pop、min都都O(1)操作了。如圖：

文字可能沒說清楚，上代碼，下面是PHP的實(shí)現(xiàn)，通過數(shù)組來模擬堆棧。

<?php
/**
 * 使用一個輔助棧，O(1)復(fù)雜度求出棧中的最小數(shù)
 * @hack 類中通過數(shù)組來模擬堆棧
 * 
 * @author laiwenhui
 */
class strack{

  /**
   * 數(shù)據(jù)棧，存儲棧數(shù)據(jù)；
   *
   * @var array
   */
  private $_arrData = array();
  /**
   * 輔助棧，存儲數(shù)據(jù)組棧中每層的最下值信息；
   *
   * @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;
    //當(dāng)前棧中最小值入棧
    array_push($this->_arrMin, $currentMin);
    //數(shù)據(jù)入棧
    array_push($this->_arrData, $element);
    $this->_top++;

    return true;
  }
  /**
   * 求當(dāng)前?？臻g的最小值
   * @return bool|int 
   */
  public function min(){
    if ($this->_top === -1){
      return false;
    }
    return $this->_arrMin[$this->_top];
  }
}

使用如下：

復(fù)制代碼代碼如下:

$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());

輸出為：

復(fù)制代碼代碼如下: