程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> 關於PHP編程 >> 用PHP解決的一個棧的面試題

用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,滿足要求。

你是否有其他更好方法實現,如果有,請告訴我^_^

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved