Preface

繼上篇【面試高頻】詳解單調堆疊，今天我們來講述一下如何用我給出的單調堆疊模板刷題，

所謂單調堆疊其實就是堆疊內元素具有單調性， 常用于解決下一個更大元素 這種問題，

我們會講一下其中最具代表性的三道題，其中一道Medium，兩道Hard，保證你看完一定有所識訓：

• 739. 每日溫度 - 力扣

• 42. 接雨水 - 力扣

• 84. 柱狀圖中最大的矩形 - 力扣

 // 單調堆疊模板，如果不懂可以看我的上篇文章
 for (遍歷這個陣列) {
     while (堆疊不為空 && 堆疊頂元素與當前陣列元素比較) {
         出堆疊；
     }
     入堆疊； 
 }

739. 每日溫度

Description

Simulation

思路：我們先列一個表格分析一下示例資料是怎么來的

首先想到的當然是暴力解法，兩層 for 回圈挨個遍歷一遍，計算天數差即可，時間復雜度O(n^2)，

get到暴力解法也很重要，畢竟不是什么時候都能想到最優解，而且我們還可以基于暴力解法進行下一步優化，

題目中要求計算下一個更高的溫度的天數差，其實就是要找到自己右邊第一個比自己大的元素， 然后計算下標之差，

很明顯要用到一個單調減（堆疊頭元素最小）的堆疊，通過O(n)的時間復雜度（即遍歷一遍）就能找到每個元素的右邊第一個比它大的元素，本質就是空間換時間，

1. 為什么是單調減？

   答：因為只有遞減的時候，我們才能得到天數差，如74放入堆疊時，73即可出堆疊，第一天的天數差就得到了，

2. 怎么計算天數差？

   答：單調堆疊內只存放元素的下標即可，需要數值比較時直接使用 t[i] 即可，

3. 模板怎么用？?

既然已經分析出要用單調堆疊，我們可以直接把三板斧（模板）使出來：

 // 模板
 stack<int> stk;
 for (int i = 0; i < t.size(); i++) {                // 遍歷溫度陣列t
     while (!stk.empty() && t[i] > t[stk.top()]) {   // 出堆疊條件，保持單調減
         stk.pop();
     }
     stk.push(i);                                    // 入堆疊，放入下標
 }

在腦中模擬一下出入堆疊的程序：

• 堆疊為空，73的下標0入堆疊，堆疊內元素 0

• 74 > 73，73出堆疊74入堆疊，天數差為1，堆疊內元素 1

• 75 > 74，74出堆疊75入堆疊，天數差為1，堆疊內元素 2

從第二步就可以看出來，我們需要在堆疊內元素出堆疊前通過下標計算天數差，增加一行即可：

     while (!stk.empty() && t[i] > t[stk.top()]) {   // 出堆疊條件，保持單調減
         res[stk.top()] = i - stk.top();    // 添加計算
         
         stk.pop();
     }

Solution

完整代碼如下，可以嘗試一下，原題鏈接：

 // hrh 8/28 
 class Solution {
 public:
     vector<int> dailyTemperatures(vector<int>& t) {
         vector<int> res(t.size());
         stack<int> stk;     
 ?
         for (int i = 0; i < t.size(); i++) {                // 遍歷
             while (!stk.empty() && t[i] > t[stk.top()]) {   // 出堆疊條件
                 res[stk.top()] = i - stk.top();             // 計算天數差值
                 stk.pop();                                  // 保持單調減
             }
             stk.push(i);                                    // 入堆疊
         }
 ?
         return res;
     }
 };

總結一下解題程序：

1. 判斷這道題能否用單調堆疊解決
2. 判斷單調性，給出三板斧
3. 模擬計算程序，刪改模板得到結果

42. 接雨水

Description

Simulation

思路：

1. 看圖分析，只有下一個大于等于自己的元素插入才會形成凹槽接到雨水，所以顯而易見，我們應該使用單調堆疊，
2. 單調性怎么判斷？很明顯，比自己小的可以直接插入，大的插入要讓前面的小元素出堆疊，因此我們需要一個遞減的堆疊（堆疊頂元素最小），
3. 面積怎么計算？底 ? 高大伙都知道，然后按行計算，下面是分析：

首先明確一下單調堆疊里到底要存什么內容，每個柱的高度？不不不！我們需要下標來計算寬度，而下標又可以直接get到對應的高度，所以只需一個單調堆疊來存盤下標就可以了，

畫了一張圖進行模擬計算程序，一組數[2,1,0,3] 從左到右依次入堆疊：

• 2入堆疊，堆疊為空，下標i直接入堆疊，堆疊內元素 i ，
• 1<2，直接入堆疊，堆疊內元素 i, i+1 ，
• 0<1，直接入堆疊，堆疊內元素 i, i+1, i+2 ，
• 3>0，保存0作為基底然后出堆疊，計算凹槽面積：高為1，選擇3與當前堆疊頂元素1之間小的那個（木桶理論，看短的）；底為1，3的下標減去1的下標 (i+3) - (i+2) ；總面積+1，繼續判斷 👇
• 3>1，保存1作為基底然后出堆疊，計算凹槽面積：高為1，因為1作為基底，此時堆疊頂元素為2，所以高為 2-1=1 ，下標計算出底為2；總面積+2，繼續判斷 👇
• 3>2，2出堆疊，但此時堆疊為空，不需要繼續計算，3終于入堆疊，最后堆疊內元素 i+3，
• 總面積為3

看完模擬程序，相信你已經有了思路，單調減的堆疊，三板斧一整，我們只需要在出堆疊的時候計算面積即可，下面給出完整代碼 🍉🍉🍉

Solution

 // hrh 8/29 
 class Solution {
 public:
     int trap(vector<int>& h) {
         stack<int> stk;    
         int res = 0;
         
         // 三板斧！
         for (int i = 0; i < h.size(); i++) {
             while (!stk.empty() && h[i] >= h[stk.top()]) {
                 int base = h[stk.top()];        // 保存基底然后出堆疊
                 stk.pop();      
                 
                 // 堆疊不空時計算面積
                 if (!stk.empty()) {             
                     int height = min(h[stk.top()], h[i]) - base;
                     int width = i - stk.top() - 1;
                     res += height*width;
                 }
             }
             
             stk.push(i);
         }
 ?
         return res;
     }
 };

84. 柱狀圖中最大的矩形

Description

Simulation

思路分析：

1. 大眼一瞧，柱狀圖高高低低，計算面積，這不是接雨水嗎？單調堆疊確認！

2. 判斷單調性？可以看到圖中都是遇到小值需要出堆疊的時候才計算面積，可以確認是遞增的堆疊，也就是堆疊頂元素最大，單調性確定！直接三板斧給出：

   

3. 單調堆疊存入下標計算寬度，根據出堆疊的最小值計算高度（具體思路上篇文章已經詳細給出，在此不贅述）刪改后可得：

for (int i = 0; i < h.size(); i++) {
    
    while (!stk.empty() && h[i] < h[stk.top()]) {	// 出堆疊條件
        int pre = stk.top();	// 保存要出堆疊的元素
        stk.pop();

        if (!stk.empty()) {		// 計算面積
            int height = h[pre];
            int width = i - stk.top() - 1;
            res = max(res, height*width);	// 保留更大的值
        }
    }
    
    stk.push(i);
}

但這樣就足夠了嗎？顯然不行，設想兩種情況：

1. 輸入兩個元素[2,5]，本身遞增可以直接入堆疊，沒有出堆疊怎么計算面積？
2. 輸入任意一個元素，怎么計算面積？

其實解決方法很簡單，我們只要在陣列前后各加一個0就可以了，0一定是最小元素，在前面加一個0不用擔心堆疊空的情況，每次出堆疊都計算一下面積；沒有出堆疊條件就創造出堆疊條件，所以在陣列后面加一個0，

h.insert(h.begin(), 0);		// 前插一個0
h.push_back(0);			    // 后插一個0

Solution

完整代碼如下：

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        stack<int> stk;
        int res = 0;
        h.insert(h.begin(), 0);
        h.push_back(0);

        for (int i = 0; i < h.size(); i++) {
    
            while (!stk.empty() && h[i] < h[stk.top()]) {	// 出堆疊條件
                int pre = stk.top();	// 保存要出堆疊的元素
                stk.pop();

                // 堆疊不會空
                int height = h[pre];
                int width = i - stk.top() - 1;
                res = max(res, height*width);	// 保留更大的值
            }
            
            stk.push(i);
        }
    
        return res;
    }

};

Conclusion

復習一下解題程序：

1. 判斷這道題能否用單調堆疊解決
2. 判斷單調性，給出三板斧
3. 模擬計算程序，刪改模板得到結果

可以看到最大矩形面積這道題跟接雨水雖然相似，但麻煩了許多，特殊值的輸入給我們的解題思路帶來了一定困擾，不過你不能指望Hard題都是套個模板就能AC的，

雖然三板斧很好用，但一些特殊條件的計算仍然是需要你自己的判斷，那么問題來了：怎么提高自己的能力？

我這里有好康的：力扣單調堆疊題庫

刷題！刷題！還是TMD刷題！！！🍗🍗

寫文不易，求個贊 💗💗

可以點個關注互相交流~

我是Mancuoj，更多有趣文章：我的個人主頁