最小堆疊問題【經典大廠面試題】

問題描述：

設計一種資料結構來存盤數字，存盤數值的范圍是 [-100000, 100000]，擁有堆疊的基礎功能（入堆疊push和出堆疊pop，后入先出），并可以隨時獲得堆疊中最小的數值，要求實作的介面有：

1. push(int)->void 放入數字，2. pop()->int 彈出并拿出堆疊頂數字，3.getMin()->int 獲得堆疊中最小數字，

其中push和pop操作要求時間復雜度O(1)，問getMin()如何實作？（盡可能讓空間復雜度和時間復雜度降低）

例子：

push 1,push 2,  此時getMin()可以獲得1. 繼續push 0，此時getMin()獲得0.  用pop()彈出堆疊頂元素后，此時getMin()獲得1.

解題思路及優化

三種getMin()實作，第一種時間復雜度O(n)，空間復雜度O(1)，第二種時間復雜度O(1)，空間復雜度O(n)，第三種時間復雜度O(1)，空間復雜度O(1)，思考難度是遞進的，

1. 時間復雜度O(n)，空間復雜度O(1)的方法

適合編程初學者理解，思路：該資料結構內部有一個鏈表(陣列也可以，但陣列需要考慮當容量滿了的擴容問題)，push會將新元素連接到鏈表尾部，pop會將尾部元素洗掉，getMin()實作方式是遍歷一遍該鏈表(陣列)，獲取最小值并回傳，

復雜度的計算：因為是遍歷，所以時間復雜度O(n)，因為getMin()并沒有申請新的輔助空間，所以空間復雜度O(1)，

C++代碼：

 1 #include<list>
 2 #include<vector>
 3 struct StackCanGetMin {
 4     std::vector<int> data;//C++中的動態陣列，可以自動擴容，
 5     void push(int value) {
 6         data.push_back(value);//直接存入元素到鏈表結尾
 7     }
 8     int pop() {
 9         int returnValue = https://www.cnblogs.com/lanhuayi/p/data.back();//先保存元素到一個變數
10         data.pop_back();//洗掉鏈表結尾元素
11         return returnValue;
12     }
13     int getMin() {
14         int minValue=https://www.cnblogs.com/lanhuayi/p/data.front();//設定minValue的值為第一個元素值
15         for (int i = 0; i < data.size();i++) {//遍歷陣列，此處方法不限只要遍歷即可
16             minValue = https://www.cnblogs.com/lanhuayi/p/std::min(data[i],minValue);//如果當前值比記錄的minValue小，就把當前值賦給minValue
17             //minValue = https://www.cnblogs.com/lanhuayi/p/data[i] 
18         }
19         return minValue;
20     }
21 };

1. 時間復雜度O(1)，空間復雜度O(n)的方法

適合編程入門者理解，思路：該資料結構內部有兩個堆疊(std::stack即可)，使用設計模式的裝飾器模式包裝第一個堆疊的push和pop方法，此外每次push時，在第二個堆疊中放入此時容器中的最小值，每次pop時，在第二個堆疊中也彈出一個值，這樣可以保證訪問getMin()時，第二個堆疊最外的值就是最小數量，

如圖：

 因為只需要比較新放入元素和之前堆疊頂的元素誰小，放入誰即可，（放入之前的堆疊頂元素就是放入之前的最小值）

復雜度的計算：需要一個額外的堆疊，存盤的元素數量和第一個堆疊元素數量相同，所以空間復雜度為O(n)，因為每次獲取直接獲得堆疊的最外元素即可，所以時間復雜度為O(1)

C++代碼如下：

 1 #include<stack>
 2 #include<algorithm>//用到該頭檔案里邊的min函式
 3 struct StackCanGetMin {
 4     std::stack<int> data;
 5     std::stack<int> storeMin;
 6     void push(int value) {
 7         data.push(value);
 8         if (storeMin.empty() == true) {//如果之前沒有元素，就無法拿出第一個元素比較
 9             storeMin.push(value);//此時直接放入即可
10         }
11         else {
12             int minValue = https://www.cnblogs.com/lanhuayi/p/std::min(storeMin.top(), value);//判斷一下之前的最小值小還是新放入的值小
13             storeMin.push(minValue);
14         }
15     }
16     int pop() {
17         data.pop();
18         storeMin.pop();
19     }
20     int getMin() {
21         return storeMin.top();
22     }
23 };

3. 時間復雜度O(1)，空間復雜度O(1)的實作

適合編程進階的人來理解，思路：一共需要一個堆疊和一個變數，變數是當前的最小值，堆疊中存盤的是和放入元素時和最小值的差值，這樣雖然沒直接存盤每個元素，但其實可以隨時計算出堆疊頂元素，pop時可以根據堆疊頂的差值和最小值計算出pop后應有的最小值，

復雜度的計算：只用到了一個額外的變數用于存盤最小值，所以空間復雜度是O(1)，并且每個操作都是根據堆疊頂元素和最小值進行計算就能得到，所以時間復雜度也是O(1)，

如圖：

push的程序： 從頭開始一步一步的講：

1. 放入第一個元素3時，因為是第一個元素，可以特殊處理，最小值為3，該元素和最小值3的差（3-3=0）是0，所以堆疊存入0.

2.放入第二個元素4時，先考慮堆疊的存盤：此時最小值為3，該元素減最小值（4-3）得1，所以堆疊存入1；最小值3和元素4比較，發現最小值不變，所以最小值仍為3

3.放入第三個元素2時，先考慮堆疊的存盤：此時最小值為3，該元素減最小值（2-3）得-1，所以堆疊存入-1；最小值3和元素2比較，發現最小值應為新的最小值，所以最小值設定為2

4.放入第四個元素5時，先考慮堆疊的存盤：此時最小值為2，該元素減最小值（5-2）得3，所以堆疊存入3；最小值2和元素5比較，發現最小值不變，所以最小值仍為2

4.放入第五個元素1時，先考慮堆疊的存盤：此時最小值為2，該元素減最小值（1-2）得-1，所以堆疊存入-1；最小值2和元素1比較，發現最小值應為新的最小值，所以最小值設定為1

放入堆疊的元素和最小值的變換程序如上，下面闡述如何根據堆疊中存盤的差值來計算出原來的元素，

top的程序(獲得堆疊頂元素，因為我們存盤的是差值所以需要一步轉換)：

情況1：如果堆疊中存盤的是正數，說明放入的元素比最小值大，并且最小值肯定沒有因為放入這個元素而改變，所以放入的元素就是 （最小值+差值），比如圖中第四個元素，

 3+2，可以得到這個元素是5，

情況2：如果堆疊中存盤的是0，和正數情況同理，放入的元素就是（最小值+0），

情況3：如果堆疊中存盤的是負數，說明放入的元素比最小值小，導致因為放入這個值，最小值發生了改變，說明這個元素就是這個最小值，如圖第三個元素放入時堆疊頂值為-1：

此時這個元素和最小值相同，值是2. 

pop的程序：

pop時主要考慮，彈出了一個元素，最小值如何維護成正確的最小值，我們可以根據彈出元素和最小值來知道上一次最小值應該是多少，
情況1：彈出元素如果是正數，比如圖中情況，我想彈出第四個，我怎么知道彈出最后最小值應該是多少，因為差值是正數，說明放入第四個元素時，第四個元素比當時的最小值大3，既然插入的值比最小值大，那么最小值肯定不會因為插入的這個值而改變，所以最小值仍為2.

情況2：彈出元素如果是0，和正數情況同理，說明新放入的元素正好和最小值相同，所以也不會改變最小值，

情況3：彈出元素如果是負數，如圖，說明放入這個元素時，這個元素比當時的最小值小，從而改變了最小值，這個元素比當時的最小值小多少呢，因為放入的是差值所以小，所以公式為：(插入元素-當時的最小值=差值) => (當時的最小值=插入元素-差值)，只需要用這個元素的值減去差值即可，而該元素的值恰好就是后來的最小值，所以最終公式為：

當時的最小值=此時的最小值-差值 ，如下圖2-(-1)=3

C++代碼如下：

 1 #include<stack>
 2 #include<algorithm>//用到該頭檔案里邊的min函式
 3 struct StackCanGetMinPerfect{
 4     std::stack<int> data;
 5     int MinValue;
 6     void push(int value) {
 7         if (data.empty()==true) {//如果堆疊為空說明放入的第一個元素，特殊處理，直接放入0
 8             data.push(0);
 9             MinValue =https://www.cnblogs.com/lanhuayi/p/ value;
10         }
11         else{
12             data.push(value-MinValue);
13             MinValue =https://www.cnblogs.com/lanhuayi/p/ std::min(value,MinValue);
14         }
15     }
16     int pop() {
17         int ReturnValue = https://www.cnblogs.com/lanhuayi/p/top();//先獲得此時的堆疊頂元素，一會當回傳值用，這步呼叫的是成員函式top，和data.top有區別
18         if (ReturnValue >= 0) {
19             MinValue = https://www.cnblogs.com/lanhuayi/p/MinValue;//其實就是不變，本行也可以不寫，寫了也會被編譯器優化掉
20         }
21         else{//如果是負數的話
22             MinValue -= data.top();//MinValue會發生改變，data.top()存盤的是一個差值，和this->top()有區別
23         }
24         data.pop();
25         return ReturnValue;
26     }
27     int top() {//通過計算得到當前堆疊頂在push時傳入的數值，
28         if (data.top() >= 0) {
29             return MinValue + data.top();
30         }
31         else {//如果最頂是負數，說明當前的最小值就是top的值
32             return MinValue;
33         }
34     }
35     int getMin() {
36         return MinValue;
37     }
38 };

有問題和錯誤歡迎在評論區提出和指正，原創文章，轉載請注明出處，謝謝大家的閱讀~

標籤：其他

上一篇：一站式交付體驗：云效+Kubernetes

下一篇：Clusternet v0.5.0 重磅發布： 全面解決多集群應用分發的差異化配置難題