用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; * 求當前?？臻g的最小值 * @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面試總結