什么是單調(diào)棧

單調(diào)棧的定義：單調(diào)棧即滿足單調(diào)性的棧結(jié)構(gòu)走敌。與單調(diào)隊(duì)列相比碴倾，其只在一端進(jìn)行進(jìn)出。

如何使用單調(diào)棧

單調(diào)棧分為單調(diào)遞增棧和單調(diào)遞減棧掉丽，顧名思義跌榔，就是棧內(nèi)元素是升序還是降序排列的，也涉及到出棧的邏輯捶障。
如下圖僧须，分別插入6,10,3,7,4,12的時(shí)候，單調(diào)遞增棧和單調(diào)遞減棧的情況分別是樣子的：

單調(diào)棧有什么應(yīng)用项炼？

能表示入棧元素左邊第一個(gè)比它的元素
能表示入棧元素左邊第一個(gè)比它的元素

我們拿上面圖的單調(diào)遞增棧來舉例說明：
源數(shù)組：[6, 10, 3, 7, 4, 12]

代碼實(shí)現(xiàn)：

//獲取左邊第一個(gè)小于自己的數(shù)，構(gòu)造一個(gè)單調(diào)遞減棧
    private int[] getLeftMinNum(int[] src) {
        int[] result = new int[src.length];
        Stack<Integer> monotoneStack = new Stack<>();
        for (int i = 0; i < src.length; i++) {
            if (monotoneStack.isEmpty()) {
                monotoneStack.push(src[i]);
                result[i] = 0;
            } else {
                while (!monotoneStack.isEmpty() && src[i] < monotoneStack.peek()) {
                    monotoneStack.pop();
                }
                if (!monotoneStack.isEmpty()) {
                    result[i] = monotoneStack.peek();
                } else {
                    result[i] = -1;
                }
                monotoneStack.push(src[i]);
            }
        }
        return result;
    }

按照這個(gè)原理墨坚，大家可以自己推一下遞增棧查找第一個(gè)小元素秧饮。

例題

例題1：BadHairDay

BadHairDay題目鏈接

Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

每頭牛只能看見右邊的牛的頭
假如牛的高度分別為 [10，3泽篮，7盗尸，4，12帽撑，2]

所以總的count = 3+1+1 = 5
思路：找到能看到的最大的牛的index泼各，比如10就只需要找到右邊第一個(gè)比自己高的牛的index，然后index-1就是自己能看到的最遠(yuǎn)的那頭牛亏拉。
所以這個(gè)問題就簡化為找到右邊第一個(gè)比自己大的數(shù)的index扣蜻，正好就是單調(diào)遞增棧的功能逆巍。

 /**
     * 10，3莽使，7锐极，4，12芳肌，2
     * 3 灵再，0，1亿笤，0翎迁， 1，0
     * 結(jié)果為5
     *
     * @param cows 數(shù)組
     * @return 結(jié)果
     */
    private int badHair(int[] cows) {
        Stack<Integer> minIndexStack = new Stack<>();
        int result = 0;
        for (int i = cows.length - 1; i >= 0; i--) {
            while (!minIndexStack.isEmpty() && cows[i] > cows[minIndexStack.peek()]) {
                //當(dāng)前元素大于棧頂元素净薛，棧頂元素比自己小需要彈出頂部元素
                minIndexStack.pop();
            }
            int bigNumIndex;
            if (minIndexStack.isEmpty()) {
                bigNumIndex = cows.length;//如果棧里沒有數(shù)據(jù)了汪榔，說明自己是最高的，可以看完整個(gè)隊(duì)伍肃拜。
            } else {
                bigNumIndex = minIndexStack.peek();
            }
            minIndexStack.push(i);
            int current = bigNumIndex - i - 1;//-1是因?yàn)榭床坏阶罡叩哪莻€(gè)揍异，所以需要把最高的刨除掉。
            result += current;
        }
        return result;
    }

例題2：接雨水

https://leetcode-cn.com/problems/trapping-rain-water/
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖爆班，計(jì)算按此排列的柱子，下雨之后能接多少雨水辱姨。

輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6

此思路借鑒自https://blog.csdn.net/qq_37236745/article/details/83795858
我們分析一下這個(gè)題目：
積水只有在左右大中間小的情況下會(huì)行成柿菩。正常的思路下我們只要找到兩遍比較大的就可以找到積水，但是如果未來出現(xiàn)更高的臺(tái)階我們必須回過頭來看之前的計(jì)算是不是有效的雨涛。
我們換種思路枢舶，一個(gè)水潭可以由底層的加上高層的組成，像下圖這樣替久。

我們同樣使用單調(diào)遞增棧，我們知道棧有兩個(gè)操作颅拦，入棧和出棧蒂誉。單調(diào)棧的出入棧表示：

入棧，表明本身比棧頂小距帅，說明在下臺(tái)階右锨，下臺(tái)階是行程不了積水的。
出棧碌秸，表明本身比棧頂大绍移，肯定會(huì)形成積水悄窃。

所以每次計(jì)算積水肯定是在pop的時(shí)候計(jì)算。而且棧里最少有兩個(gè)元素的時(shí)候才會(huì)形成蹂窖，因?yàn)樽钚〉姆e水也是有兩個(gè)邊和一個(gè)坑組成的轧抗，最少也是棧里兩個(gè)加上剛來的一個(gè)。
這里我們可以想象成一個(gè)木桶恼策，根據(jù)木桶理論鸦致，容量由最低的那塊木板決定，所以桶的容量需要由 長木板+桶底+短木板決定
我們看上面圖的例子：

• 遍歷到3的時(shí)候涣楷。棧：[1, 0]分唾，來了一個(gè)2，2比0大狮斗，0要出棧绽乔，這個(gè)時(shí)候就可以知道1和2中間夾了一個(gè)0，找1和2最小值碳褒，短木板是1折砸，桶底是0，所以寬度是1沙峻，高度是1睦授，得到面積是1.
• 遍歷到6的時(shí)候。棧：[2摔寨，1去枷，0]，來了1是复，所以1和1中間夾了0删顶，同樣得到面積是1，得到的是淺藍(lán)色的部分淑廊。
• 繼續(xù)往后遍歷來到7逗余，來了一個(gè)3，棧：[2,1] (看入棧的邏輯季惩，棧里也可以是[2,1,1]录粱，相同的1可以入可以不入)。假設(shè)是[2,1]画拾，先彈1关摇，短木板是1，長木板是3碾阁，但是桶底也是1输虱，所以能裝的水是0。1彈出之后棧里還剩[2]脂凶，短木板是2宪睹，長木板是3愁茁，桶底是1，水深度為1亭病，寬度index=6-3=3鹅很，所以面積是3.

代碼實(shí)現(xiàn)：

private int trap(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        int sumArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int right = 0; right < height.length; right++) {
            while (!stack.isEmpty() && height[stack.peek()] <= height[right]) {
                if (stack.size() >= 2) {
                    int j = stack.pop();
                    int left = stack.peek();
                    int waterHeight = Math.min(height[right], height[left]) - height[j];//就像一個(gè)木桶：得到最低的木板減去底得到能裝水的高度
                    int waterLength = right - left - 1;
                    int curArea = waterHeight * waterLength;
                    sumArea += curArea;
                } else {
                    stack.pop();
                }
            }
            stack.push(right);
        }
        return sumArea;
    }