什么是棧

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

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

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

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

棧這種數(shù)據(jù)結(jié)構(gòu)既可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。

棧的數(shù)組實現(xiàn)如下。

棧的鏈表實現(xiàn)如下。

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

棧的基本操作

入棧

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

這里我們以數(shù)組實現(xiàn)為例。

出棧

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

這里我們以數(shù)組實現(xiàn)為例。

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

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

現(xiàn)，入棧、出棧的時間復(fù)雜度都是O(1) 。

什么是單調(diào)棧

單調(diào)遞增棧 從棧底到棧頂?shù)脑仃P(guān)鍵字的大小單調(diào)遞增；

單調(diào)遞減棧 從棧底到棧頂?shù)脑仃P(guān)鍵字的大小單調(diào)遞減；

適用問題：

要知道單調(diào)棧的適用于解決什么樣的問題，我們首先需要知道單調(diào)棧的作用。單調(diào)棧分為單調(diào)遞增棧和單調(diào)遞減棧，通過使用單調(diào)棧我們可以訪問到下一個比他大（?。┑脑兀ɑ蛘哒f可以）。

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

舉個栗子

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

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

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

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

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

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

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

（6）柯鎮(zhèn)惡來了，打不過，站到后面就好了。

（7）然后喬峰來了把柯鎮(zhèn)惡和張無忌打發(fā)走， —現(xiàn)在隊里有掃地僧，喬峰。

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

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

現(xiàn)在看他們分別學(xué)到武功對應(yīng)如下圖：

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

偽代碼如下所示：

對于第i個到來的人：

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

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

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

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

單調(diào)棧實現(xiàn)：尋找兩邊距離arr[i]最近且arr[i]小的索引，保持棧頂?shù)綏５讍握{(diào)遞減，棧中存放索引值。

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

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.接雨水

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

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

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

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;
    }
}