單調堆疊

總得來說這相當于是一堂“習題課”，
Theme is “Monum Stack”.
（記得上次仿佛說還要講一哈優先佇列priority_queue，但著實又感覺沒有啥特別好講的，其類似于一個大頂堆（heap，我們會在排序章節講到堆排序），就是說基本情況下，優先佇列的總是會把最大的數放在隊頭！！）
本次就由淺入深準備了三道題，現在來集合成一個題解，

題一：

相信見到這種題目甭管大神不大神第一思路都是暴力吧， 因為簡單，通俗易懂，
暴力思路如下：
每遍歷到一個數就從其之后開始尋找第一個比其大的數，找到的話就用下標差記入答案中，否則記入0到答案中，
代碼就不給出了，確實是非常簡單的了，但簡單的代碼存在了一個巨大的問題就是其是O(n2)的時間復雜度，這意味著你面試可能就gg了，

那既然我們開篇就給出了單調堆疊的思想，我們如何來設計并且維護呢？
思路如下：
每每遍歷到一個數字我們就將其與堆疊頂元素去進行比較，
如果堆疊為空（即無堆疊頂元素），直接將此下標入堆疊，
如果此元素比堆疊頂元素小，那么也直接入堆疊，
倘若比當前堆疊頂元素要大！那么我們就相當于找到了第一個比當前堆疊頂元素的氣溫要高的日子，用下標相減得到等待天數，此外，我們將當前堆疊頂元素彈出，并且持續判斷與堆疊頂元素的大小關系，如果仍舊比其大就重復上述操作，如果堆疊空了或者不比堆疊頂大了的話就將當前這個下標入堆疊，

通過以上操作我們可以發現比較高的氣溫會被壓在堆疊底，而一旦找到了氣溫升高的日子就會從堆疊頂不斷彈出元素并且持續進行比較，

我相信語言還是沒法講清楚，所以畫個圖解釋或許會較好，
我們按照思路走一遍流程圖：
入堆疊的都是下標！

一開始堆疊為空，無需多余操作，直接入堆疊，

下標為1時，由于74 > 73，直接會pop堆疊頂元素，然后會把答案，即間隔 1 - 0 = 1存入vector容器中，同時會把1入堆疊，

此情況與上相同！不贅述！

下標為5的氣溫會比4和3都要高，直接計算出答案彈出堆疊頂最后放入5即可，
后面的程序都是類似的，要注意的就是最后留在堆疊內的元素都是找不到比其更高的氣溫的，因此都是用0填充，

這里要注意一個小問題，答案容器要求回傳vector，但實際上我們并不是按順序一個一個計算出答案然后用push_back的方式存入答案的！

即注意上圖，我們發現下標為4的會比下標為3的先計算出答案！！！
這樣一來就要求我們要事先宣告好容器的大小，然后直接利用索引的方式進行值的修改即可！
還有一點需要注意的就是直接宣告大小會使此容器填充滿0，
最后實作代碼如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> v(T.size()); // 直接宣告了大小，會填充滿0
        stack<int> s;
        for(int i = 0 ; i < T.size() ; i ++){
        // 不斷與堆疊頂元素作比較，比其大的話就回圈操作
            while(!s.empty() && T[i] > T[s.top()]){
            // 用下標索引的方式修改原先的0為計算出來的值
            // 不能直接push_back的原因上面有闡述
                v[s.top()] = i - s.top();
                s.pop();
            }
            s.push(i);
        }
        // 若堆疊記憶體在未處理的元素不需另外操作，因為我們初始化就是用0填充的
        // 因此現在無需修改，
        return v;
    }
};

題二

此題是上次堆疊沒有講清楚的題最大矩形面積，

肯定不排除那些看一眼代碼就知道解題思路的大佬的存在啦，
不過呢，做事講究個完整，還是把上次沒講的思路補上，
實際上這題的思想和上題類似，但需要多考慮一步！

演算法思想如下：
遍歷每一個元素，
如若堆疊為空，下標直接進堆疊，
如若堆疊不為空，如果遍歷到的當前下標所對應的高小于堆疊頂元素對應的高那么由堆疊頂高所成的最大矩形就可以確定了，此矩形高就是堆疊頂元素，寬就是當前遍歷下標和堆疊頂下標之差，然后堆疊頂元素出堆疊，遍歷到的當前下標進堆疊，
如若堆疊不為空，如果當前遍歷到的下標所對應的高大于堆疊頂元素對應的高那么堆疊頂元素所形成的矩形實際上還可以繼續擴張面積仍舊不能確定，因此僅需讓遍歷到的當前下標進堆疊即可，

這兒之后會比上面的氣溫題多出一些步驟！
我們的堆疊也會存在遍歷完一遍陣列后堆疊中還有元素的現象，此時不能直接忽略，因為此時堆疊中殘留元素的含義是：
以此下標對應的高，一直遍歷到陣列末尾都沒有再比此高度更矮的數存在，其實翻譯過來就是說，矩形一直可以從此下標開始延伸到陣列末尾，
因此，在遍歷完一遍陣列后如果堆疊中有殘余，就計算輸入陣列的size - 當前堆疊頂的下標 - 1為寬，且當前堆疊頂對應到陣列索引值為高計算出面積，并且不斷彈出堆疊頂元素直至處理完畢，

實際上思路真的和上題差不多，因此不再附圖示，主要是后面多出來的這一步要好好理解，代碼如下：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int area = 0;
        for(int i = 0 ; i < heights.size() ; i ++){
            while(!s.empty() && heights[i] < heights[s.top()]){
                int height = heights[s.top()];
                s.pop();
                int width = i;
                if(!s.empty()){
                    width = i - s.top() - 1;
                }
                area = max(area, height * width);
            }
            s.push(i);
        }
        while(!s.empty()){
            int height = heights[s.top()];
            s.pop();
            int width = heights.size();
            if(!s.empty()){
                width = heights.size() - s.top() - 1;
            }
            area = max(area, height * width);
        }
        return area;
    }
};

此代碼實際上還可以進行常數的優化，因此單純上面的代碼實際上效率還稱不上特別高，如果想要深究可以看到官方題解----官方最大矩形題解，

題三

**個人認為這道題是相較于前兩題偏難一些的，純屬個人感覺哈， **

首先我們要意識到雨水被接收在凹槽中，也就是說當存在一個兩邊高中間低的情況時我們就能求出雨水量，相信這個無論從常識還是理論方面都好理解，

于是乎，我們會維護一個遞減單調堆疊！遞增沒意義啊，因為我們要的是兩邊高，中間低啊！

整體思路如下，以題目給出的例子為基準：
首先對于陣列首元素，當其為0時實際上是無意義的，因此我們直接對索引為0的地方進行單獨性判斷，若值為0，就不予理睬，否則將下標進堆疊，

然后依次往后遍歷元素，當遍歷到的元素比堆疊頂元素嚴格小或者當前堆疊為空時就另其直接進堆疊，

于是紅框內兩下標元素直接進堆疊！

再往后遍歷就會遇到比堆疊頂要大的下標3，其對應高度為2，
由于單調堆疊的特性，我們知道，假如我們把當前堆疊頂元素彈出后堆疊還不為空的話那么必然就存在一個凹槽了，因為當前堆疊頂前肯定有比當前堆疊頂要高的元素的存在，又因為當前又遍歷尋找到比當前堆疊頂高的元素，那么就證明可以積攢雨水了，

于是，當遍歷到下標3時，我們會先彈出堆疊頂元素，然后判斷堆疊是否為空，若為空，那么直接將現在遍歷的下標3進堆疊，
如若不為空，我們取min(height[3], height[s.top()])，用此值來減去剛剛彈出的元素索引對應的高，乘上3 - s.top() - 1（代表矩形的寬），求出相應的雨水量，然后再次彈出堆疊頂，再做判斷，

總得來說，就是當遍歷到的當前高要嚴格大于當前堆疊頂索引對應的高時，有如下操作：
保存當前堆疊頂并彈出當前堆疊頂，
若堆疊空了，那么就是說明沒有凹槽無法積攢雨水，直接跳出回圈，
若此時堆疊未空！那么實際上當前遍歷的高和當前堆疊頂對應的高就是高的兩端，而剛剛彈出的元素就是那部分低的槽的高度，
畫個抽象的容器，

計算方法當然就是用兩端里較矮的那個高來減去凹槽的高度最后乘上兩個索引的差值作為寬得到盛水量，然后重復上述操作，

這個演算法的思想實際上就是一層層地計算雨水量，

這里提供更為優秀清晰的題解—接雨水題解，

代碼如下：

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0)
            return 0;
        stack<int> s;
        int water = 0;
        if(height[0] != 0)
            s.push(0);
        for(int i = 1 ; i < height.size() ; i ++){
            if(s.empty() || (!s.empty() && height[i] < height[s.top()]))
                s.push(i);
            else{
                while(!s.empty() && height[i] > height[s.top()]){
                    int temp = s.top();
                    s.pop();
                    if(!s.empty()){
                        water += (min(height[s.top()], height[i]) - height[temp]) * (i - s.top() - 1);
                    }
                    else{
                        break;
                    }
                }
                s.push(i);
            }
        }
        return water;
    }
};

艱辛的錯誤歷程就不贅述了，

快過年了，很放松，效率低下，damn！

祝大噶活新年快樂啊！