什么是棧

要弄明白什么是棧，我們需要先舉一個生活中的例子。

假如有一個又細又長的圓筒，圓筒一端封閉，另一端開口。往圓筒里放入乒乓球，先放入的靠近圓筒底部，后放入的靠近圓筒入口。

那么，要想取出這些乒乓球，則只能按照和放入順序相反的順序來取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球優先取出。

棧（stack）是一種線性數據結構，它就像一個上圖所示的放入乒乓球的圓筒容器，棧中的元素只能先入后出（First In Last Out，簡稱FILO ）。最早進入的元素存放的位置叫作棧底（bottom），最后進入的元素存放的位置叫作棧頂（top）。

棧這種數據結構既可以用數組來實現，也可以用鏈表來實現。

棧的數組實現如下。

棧的鏈表實現如下。

那么，棧可以進行哪些操作呢？棧的最基本操作是入棧和出棧，下面讓我們來看一看。

棧的基本操作

入棧

入棧操作（push）就是把新元素放入棧中，只允許從棧頂一側放入元素，新元素的位置將會成為新的棧頂。

這里我們以數組實現為例。

出棧

出棧操作（pop）就是把元素從棧中彈出，只有棧頂元素才允許出棧，出棧元素的前一個元素將會成為新的棧頂。

這里我們以數組實現為例。

入棧和出棧操作，時間復雜度分別是多少？

入棧和出棧只會影響到最后一個元素，不涉及其他元素的整體移動，所以無論是以數組還是以鏈表實

現，入棧、出棧的時間復雜度都是O(1) 。

什么是單調棧

單調遞增棧 從棧底到棧頂的元素關鍵字的大小單調遞增；

單調遞減棧 從棧底到棧頂的元素關鍵字的大小單調遞減；

適用問題：

要知道單調棧的適用于解決什么樣的問題，我們首先需要知道單調棧的作用。單調棧分為單調遞增棧和單調遞減棧，通過使用單調棧我們可以訪問到下一個比他大（小）的元素（或者說可以）。

也就是說在隊列或數組中，我們需要通過比較前后元素的大小關系來解決問題時我們通常使用單調棧。

舉個栗子

有一個地方要傳授武林秘籍，大家要在這一天之前來這里排好隊等著學習武林秘籍。來了很多武林高手，但是這個地方的人要根據人來的先后順序教，先來的學的武功就高深，來的越靠后學的就越差，但是能保證只要來就能學到。假如他們一開始有一個初始的排隊順序和武力水平如下所示，大家可以按照這個初始順序從前往后學習。

問題來了，武力值高的肯定愿意先學習到高深一點的武功啊，那我就找到前面武力值低的人說：“你別學了，我教你一門武功，然后離開，否則就咔嚓了你??”，武力值低的那聽就答應了也就只能無可奈何的打印了，從后來的那個人那里哪里學了一門武術就離開了，這樣武功高的那個就排在了前面。下面我們來從前往后模擬一下過程：

（1）首先來的是炮灰甲，炮灰甲一看，OK，棧內沒有人就可以先排在第一位

（2）然后掃地僧來了，掃地僧教給了炮灰甲一招易筋經，然后掃地僧讓炮灰甲離開自己排在第一位。

（3）然后楊過過來，看到前面是掃地僧，自己打不過只能老老實實站到隊里。

（4）后面一直來人（如3）------ 直到張三對里面站的是掃地僧楊過慕容復張三。

（5）然后張無忌來了，他首先看到前面是張三，張無忌教給張三一招武當梯云縱，然后讓張三離開了，張無忌再往前看到了慕容復教他一招太極拳，然后繼續直到遇到掃地僧，OK，自己打不過，老老實實的占到了后面 —現在隊里有掃地僧，張無忌 ----楊過，慕容復，張三的師傅為張無忌

（6）柯鎮惡來了，打不過，站到后面就好了。

（7）然后喬峰來了把柯鎮惡和張無忌打發走， —現在隊里有掃地僧，喬峰。

（8）然后李四來了，打不過喬峰，只能站到了最后。

（9）第二天掃地僧，喬峰，李四成功學到了武林秘籍

現在看他們分別學到武功對應如下圖：

這樣我們就處理完了所有過程。因此單調棧的時間復雜度為O(n),在比較時對出棧的元素有一個處理（例如掃地僧讓炮灰甲走的時候教給他自己的武功），另外最后留在站內的元素有一個統一的處理（掃地僧，喬峰，李四成功學到了武林秘籍）。

偽代碼如下所示：

對于第i個到來的人：

每當隊里面有人并且打不過自己的時候：

- 讓這個人離開并交給他自己的武功
- 自己入隊

LCR 039. 柱狀圖中最大的矩形

思路：有了單調棧的基本認識，我們可以遍歷每根柱子，以當前柱子 i 的高度作為矩形的高，那么矩形的寬度邊界即為向左找到第一個高度小于當前柱體 i 的柱體，向右找到第一個高度小于當前柱體 i 的柱體。對于每個柱子我們都如上計算一遍以當前柱子作為高的矩形面積，最終比較出最大的矩形面積即可。

單調棧實現：尋找兩邊距離arr[i]最近且arr[i]小的索引，保持棧頂到棧底單調遞減，棧中存放索引值。

注意：頭0如果不添加，尋找左邊元素需要判斷棧是否為空；尾0如果不添加，需要重新寫一個循環彈出棧內元素。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int [] left = new int[n];
        int [] right = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                stack.pop();
            }
            left[i] = (stack.isEmpty() ? -1: stack.peek());
            stack.push(i);
        }
        stack.clear();
        for(int i = n-1; i >= 0; i--){
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                stack.pop();
            }
            right[i] = (stack.isEmpty() ? n : stack.peek());
            stack.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
}

42.接雨水

該題目有多種解法，本次只介紹單調棧的方式，對其它算法感興趣的朋友可以自己去嘗試一下~~

思路：理解題目注意題目的性質，當后面的柱子高度比前面的低時，是無法接雨水的，當找到一根比前面高的柱子，就可以計算接到的雨水。所以使用單調遞減棧：

對更低的柱子入棧，更低的柱子以為這后面如果能找到高柱子(可以理解為代碼中的 left )，這里就能接到雨水，所以入棧把它保存起來。
當出現高于棧頂（代碼中 top）的柱子時說明可以對前面的柱子結算了

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}