什么是棧

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

假如有一個(gè)又細(xì)又長(zhǎng)的圓筒，圓筒一端封閉，另一端開(kāi)口。往圓筒里放 入乒乓球，先放入的靠近圓筒底部，后放入的靠近圓筒入口。

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

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

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

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

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

那么，棧可以進(jìn)行哪些操作呢？棧的最基本操作是入棧和出棧，下面讓我們來(lái)看一看。

棧的基本操作

入棧

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

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

出棧

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

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

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

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

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

什么是單調(diào)棧

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

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

適用問(wèn)題：

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

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

舉個(gè)栗子

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

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

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

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

（3）然后楊過(guò)過(guò)來(lái)，看到前面是掃地僧，自己打不過(guò)只能老老實(shí)實(shí)站到隊(duì)里。

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

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

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

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

（8）然后李四來(lái)了，打不過(guò)喬峰，只能站到了最后。

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

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

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

偽代碼如下所示：

對(duì)于第i個(gè)到來(lái)的人：

• 每當(dāng)隊(duì)里面有人并且打不過(guò)自己的時(shí)候：

• 讓這個(gè)人離開(kāi)并交給他自己的武功
• 自己入隊(duì)

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

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

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

注意：頭0如果不添加，尋找左邊元素需要判斷棧是否為空；尾0如果不添加，需要重新寫(xiě)一個(gè)循環(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)棧的方式，對(duì)其它算法感興趣的朋友可以自己去嘗試一下~~

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

• 對(duì)更低的柱子入棧，更低的柱子以為這后面如果能找到高柱子(可以理解為 代碼中的 left )，這里就能接到雨水，所以入棧把它保存起來(lái)。
• 當(dāng)出現(xiàn)高于棧頂（代碼中 top）的柱子時(shí)說(shuō)明可以對(duì)前面的柱子結(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;
    }
}