單調堆疊

這是筆者的第一篇博客，由于筆者自身水平的限制，用詞可能不夠準確，句子不太通順，代碼水平可能也不太行，敬請指出，感激不盡！

我們都知道堆疊（Stack）是一種先入后出的資料結構，而單調堆疊建立在堆疊的基礎上，它區別于普通的堆疊的特殊之處在于

堆疊中的元素一直保持著單調遞增/單調遞減的關系

比如單調遞增堆疊中的元素自堆疊底至堆疊頂元素（0~n-1）間都是單調遞增的，單調遞減堆疊中的元素都是單調遞減的，

為了加深印象，我們可以先以單調遞減堆疊為例，看一個例子~

有一組數nums[6] = {10，1，8，12，6，4}按照如下規則進行操作：

1. 如果堆疊為空/正在處理的數小于堆疊頂的數，則進堆疊；
2. 如果正在處理的數大于堆疊頂的數，則將堆疊頂元素出堆疊，然后繼續進行判斷，

OK，首先我們將堆疊置空，然后再來一個一個地讀數，

1. 首先讀到了10，此時堆疊為空，10進堆疊，現在堆疊的狀態： {10}

2. 讀到了1，堆疊頂元素為10，1<10，1進堆疊，堆疊的狀態： {10 ， 1}

3. 讀到8，堆疊頂元素為1，8>1，那么我們將1出堆疊；

   繼續判斷，8<10，所以8進堆疊，堆疊的狀態： {10，8}

4. 讀到數12，堆疊頂元素為8，12>8，將8出堆疊；

   繼續判斷，12>10，所以10出堆疊，此時堆疊已為空，將12進堆疊： {12}

5. 讀到6，6<12，進堆疊；{12，6}

6. 讀到4，4<6，將4進堆疊， {12，6，4}

讀到這邊，相信讀者對單調堆疊的基本操作已經稍微有了解啦，那么，單調堆疊有什么用呢？

還是看上面的例子，假設我們用單調堆疊處理上面的陣列并且得到另外一個陣列（假設陣列名為arr，并且將該陣列初始化為0），規定：在處理每個數（nums[i]）之后，如果nums[i]保持在堆疊中，則將arr[i]自增1，那么處理完整個陣列之后，得到的arr陣列應該是：{3，1，1，3，2，1}，不難發現，arr[i]代表的含義是：

自第i個元素開始，從左往右數的連續的比它小的數的個數

通過單調堆疊的資料結構，我們可以很容易地得到這個陣列（很容易知道一個元素附近的數和它之間的大小關系）（只需要O(n)的時間），所以，如果問題中經常需要判斷陣列前后元素的大小關系，不妨采用單調堆疊的資料結構，

這樣看可能讀者理解不夠透徹，印象不夠深刻，那不妨一起來看道例題吧~

接雨水

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水，

示例 1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 輸出：6 解釋：上面是由陣列
[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水），

示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

看完題目之后我們可以先來分析一下，按照從左邊開始數第i個位置上可以盛放的水的量 = min(該柱子左邊最高柱子的高度，該柱子右邊最高柱子的高度) - 該柱子的高度，

方法一：

自左往右暴力列舉每個柱子左邊最高柱子的高度和右邊最高柱子的高度，相加最后可得結果，時間復雜度為O(n2)，

方法二：

不難看出我們需要經常比較每個位置柱子高度和其左右柱子高度，所以不妨建一個單調堆疊來模擬這個程序：

（為了方便看，我們假設目前讀到的柱子高度為heights[i]，堆疊中存放柱子的編號（自左往右0~n-1）,堆疊的高度為Size）

1. 若堆疊為空（Size==0）或 柱子高度小于堆疊頂柱子高度（heights[i] < heights[stack[Size-1]]），則進堆疊；
2. 若柱子高度大于等于堆疊底柱子（為此時左邊最高的柱子）高度（heights[i] >= heights[stack[0]]），堆疊中除堆疊底外的每個格子可以多盛放heights[stack[0]] - heights[stack[j]] 個單位的雨水；
3. 若柱子高度大于堆疊頂柱子高度且小于堆疊底柱子高度（heights[i] >= heights[stack[Size-1]]），則堆疊頂元素對應的柱子可以多盛放heights[i] - heights[stack[Size - 1]]個單位的雨水，（在更新了答案ans的值后，我們不妨令堆疊頂元素對應的柱子高度等于heights[i]）

就上方第一個例子做個示范：

1. 讀入高度heights[0] = 0，進堆疊，

2. 讀入高度heights[1] = 1,大于堆疊底元素，將堆疊底元素出堆疊（因為此時堆疊中只有一個元素，所以不需要對ans進行操作），再將heights[1]進堆疊，

3. 讀入元素heights[2] = 0,小于堆疊頂元素，進堆疊，
   

4. 讀入元素heights[3] = 2，大于堆疊底元素，將堆疊中所有元素彈出，此時因為heights[2] = 0 而 heights[1] = 1 ，所以可以多盛 1-0=1個單位的雨水，將ans + 1，然后將heights[3]進堆疊，
   

5. 讀入元素heights[4] = 1，進堆疊，讀入元素heights[5] = 0，進堆疊，
   

6. 讀入元素heights[6] = 1，這里heights[6] > heights[5] 且heights[6] < heights[3] ，我們將ans加上heights[6] - heights[5]之后，令heights[5] = heights[6] ，繼續判斷，heights[4] = heights[6] ， heights[6]進堆疊，
   

7. 讀入元素heights[7] = 3，這里heights[7] > heights[3] （堆疊底元素），所以要將堆疊中所有元素彈出，heights[4]，heights[5]，heights[6] 加上其與heights[3] 的差值，并且更新ans，然后將heights[7]進堆疊，
   

8. 后面的步驟都只是重復前面的，所以這邊直接跳過，值得注意的是，最后堆疊中仍有五個元素，但因為右邊是空的，無法盛水，所以無需出堆疊，保持原樣即可，

   代碼實作（C語言）：

   int trap(int* height, int heightSize){
       int stack[1000];
       int top = 0,i;
       int ans = 0;
       for(i=0;i<heightSize;i++){
           if(top==0){	//如果堆疊為空，直接進堆疊
               stack[0] = i;
               top++;
           }else if(height[i] >= height[stack[0]]){ //如果讀到元素大于堆疊底元素高度，將堆疊置空后進堆疊
               int j;
               for(j=1;j<top;j++){
                   ans += height[stack[0]] - height[stack[j]];
                   height[stack[j]] = heights[stack[0]]
               }
               stack[0] = i;
               top = 1;
           }else{
               int j=1;
               while(height[i]>height[stack[top-j]]){ 
                   ans += height[i] - height[stack[top-j]];
                   height[stack[top-j]] = height[i];
                   j++;
               }
               stack[top] = i;
               top++;
           }
       }
       return ans;
   }
   

限于筆者的水平，文章或者代碼中可能存在錯誤或者疏漏，請讀者不吝指正，感激不盡！