单调栈和应用实践

什么是单调栈

单调栈的定义：单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

如何使用单调栈

单调栈分为单调递增栈和单调递减栈，顾名思义，就是栈内元素是升序还是降序排列的，也涉及到出栈的逻辑。
如下图，分别插入6,10,3,7,4,12的时候，单调递增栈和单调递减栈的情况分别是样子的：

单调栈有什么应用？

能表示入栈元素左边第一个比它的元素
能表示入栈元素左边第一个比它的元素

我们拿上面图的单调递增栈来举例说明：
源数组：[6, 10, 3, 7, 4, 12]

处理元素	单调栈内	找到元素	补充说明
6	[6]	无	栈为空，说明左边没有比它大的了
10	[10]	无	栈顶元素6比自己(10)小，为了维持单调递减，6出栈，10入栈
3	[10, 3]	10	3比10小，直接入栈
7	[10, 7]	10	7比3大，为了不保证递减，3出栈，7入栈
4	[10, 7, 4]	7	4比7小，直接入栈
12	[12]	无	12比栈里所有元素都大，弹完后栈空，找不到比自己大的。

代码实现：

//获取左边第一个小于自己的数，构造一个单调递减栈
    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;
    }

按照这个原理，大家可以自己推一下递增栈查找第一个小元素。

例题

例题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]

index	自己的高度	能看到哪几头	数量
0	10	3,7,4	3
1	3	null	0
2	7	4	1
3	4	null	0
4	12	2	1
5	2	null	0

所以总的count = 3+1+1 = 5
思路：找到能看到的最大的牛的index，比如10就只需要找到右边第一个比自己高的牛的index，然后index-1就是自己能看到的最远的那头牛。
所以这个问题就简化为找到右边第一个比自己大的数的index，正好就是单调递增栈的功能。

 /**
     * 10，3，7，4，12，2
     * 3 ，0，1，0， 1，0
     * 结果为5
     *
     * @param cows 数组
     * @return 结果
     */
    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()]) {
                //当前元素大于栈顶元素，栈顶元素比自己小需要弹出顶部元素
                minIndexStack.pop();
            }
            int bigNumIndex;
            if (minIndexStack.isEmpty()) {
                bigNumIndex = cows.length;//如果栈里没有数据了，说明自己是最高的，可以看完整个队伍。
            } else {
                bigNumIndex = minIndexStack.peek();
            }
            minIndexStack.push(i);
            int current = bigNumIndex - i - 1;//-1是因为看不到最高的那个，所以需要把最高的刨除掉。
            result += current;
        }
        return result;
    }

例题2：接雨水

https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

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

此思路借鉴自https://blog.csdn.net/qq_37236745/article/details/83795858
我们分析一下这个题目：
积水只有在左右大中间小的情况下会行成。正常的思路下我们只要找到两遍比较大的就可以找到积水，但是如果未来出现更高的台阶我们必须回过头来看之前的计算是不是有效的。
我们换种思路，一个水潭可以由底层的加上高层的组成，像下图这样。

而且这两个可以不影响，我们可以先得到浅蓝色的部分，后面如果出现更高的再加上深蓝色的部分。如果不出现就不加。

我们同样使用单调递增栈，我们知道栈有两个操作，入栈和出栈。单调栈的出入栈表示：

入栈，表明本身比栈顶小，说明在下台阶，下台阶是行程不了积水的。
出栈，表明本身比栈顶大，肯定会形成积水。

所以每次计算积水肯定是在pop的时候计算。而且栈里最少有两个元素的时候才会形成，因为最小的积水也是有两个边和一个坑组成的，最少也是栈里两个加上刚来的一个。
这里我们可以想象成一个木桶，根据木桶理论，容量由最低的那块木板决定，所以桶的容量需要由 长木板+桶底+短木板决定
我们看上面图的例子：

• 遍历到3的时候。栈：[1, 0]，来了一个2，2比0大，0要出栈，这个时候就可以知道1和2中间夹了一个0，找1和2最小值，短木板是1，桶底是0，所以宽度是1，高度是1，得到面积是1.
• 遍历到6的时候。栈：[2，1，0]，来了1，所以1和1中间夹了0，同样得到面积是1，得到的是浅蓝色的部分。
• 继续往后遍历来到7，来了一个3，栈：[2,1] (看入栈的逻辑，栈里也可以是[2,1,1]，相同的1可以入可以不入)。假设是[2,1]，先弹1，短木板是1，长木板是3，但是桶底也是1，所以能装的水是0。1弹出之后栈里还剩[2]，短木板是2，长木板是3，桶底是1，水深度为1，宽度index=6-3=3，所以面积是3.

代码实现：

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];//就像一个木桶：得到最低的木板减去底得到能装水的高度
                    int waterLength = right - left - 1;
                    int curArea = waterHeight * waterLength;
                    sumArea += curArea;
                } else {
                    stack.pop();
                }
            }
            stack.push(right);
        }
        return sumArea;
    }