单调栈的理解及2个例子

一、 概念

单调栈是一种特殊的栈结构，它可以在O(n)的时间复杂度内，找到数组中每个元素向左或向右的第一个比它大或小的元素。单调栈的特性是栈内元素保持单调性，可以是单调递增也可以是单调递减。

单调栈的工作原理如下：

单调递增栈:

1. 如果新来的元素比栈顶元素大，就将新元素加到栈顶。
2. 如果新来的元素比栈顶元素小，加入会破坏了栈的单调递增性，就将栈顶元素移除，直到栈为空或栈顶元素比新元素小。在出栈的过程中，对于每一个被移除的元素，都比新元素大，且新元素就是它右边第一个比它小的元素。

单调递减栈:

1. 新来的元素比栈顶元素小，就将新元素加到栈顶。
2. 如果新来的元素比栈顶元素大，加入会破坏了栈的单调递减性，就将栈顶元素移除，直到栈为空或栈顶元素比新元素大。在出栈的过程中，对于每一个被移除的元素，都比新元素小，且新元素就是它右边第一个比它大的元素。

单调栈在解决一些查找元素两侧第一个大于或小于其的元素的问题中非常有用，单调栈中通常存的是数组的索引。

二、 柱状图中最大的矩形

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

柱状图中最大的矩形_1.jpg

示例 2：
输入：heights = [2,4]
输出：4

柱状图中最大的矩形_2.jpg

提示：

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

思路一:

容易想到, 对于每一个元素, 用while求出它左右第一个比它小的元素坐标差(即宽度), 再乘以自身高度即是当前元素能构造出的最大面积
但这样会存在多次重复计算, 时间复杂度来到O(n ^ 2), 实在不理想

思路二:

构造单调递增栈, 当新元素比栈内元素小时, 栈内元素出栈并计算其最大面积
对于每一个出栈的元素, 栈左边第一个比它小的元素, 就是其左边起点left, 新元素位置是其右边终点r, (r-left-1) *自身高度 即是出栈元素能构成的最大面积

java代码实现:

public int largestRectangleArea_monoStack(int[] heights) {
        int[] tmp = new int[heights.length+2];
        int maxArea = 0;
        System.arraycopy(heights, 0, tmp, 1, heights.length);
        // 单调栈存的是索引
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tmp.length; i++) {
            // 下一个元素如果比栈内元素对应索引的高度小,则出栈
            // 因为已出栈的索引对应的高度,肯定比还在栈内索引对应的高,所以可以连续出栈
            while (!stack.isEmpty() && tmp[stack.peek()] > tmp[i]) {
                int h = tmp[stack.pop()];
                while (!stack.isEmpty() && h == tmp[stack.peek()]) {
                    stack.pop();
                }
                int w = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, w * h);
            }
            stack.push(i);
        }
        return maxArea;
    }

思考: 本题确实能使用单调栈解答, 有更优的解法吗?

三、 接雨水

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

接雨水.png

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

思路:

构造单调递减栈, 当新元素大于栈内元素时, 栈内元素出栈, 并计算当前柱子加上左右两根柱子可接多少雨水
对于每一个出栈的元素, 栈左边第一个比它大的元素, 就是其左边起点left, 新元素位置是其右边终点r, (r-left-1) *自身高度 即是出栈元素能借下的雨水

java代码实现:

public int trap_monoStack(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int capacity = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int h1 = height[stack.pop()];
                while (!stack.isEmpty() && h1 == height[stack.peek()]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    break;
                }
                int h2 = Math.min(height[stack.peek()], height[i]);
                capacity += (h2 - h1) * (i - stack.peek() - 1);

            }
            stack.push(i);
        }
        return capacity;
    }

思考: 本题确实能使用单调栈解答, 但是有更优的解法吗?








确实有更优的解法:

单调栈的缺点是, 频繁的入栈出栈会比较消耗CPU, 于是考虑多读少写的解法
容易想到, 对于每一个元素, Math.min(它左边最高, 它右边最高) - 当前值 , 结果大于0时, 即是其能够接下的最多雨水
因此, 做两次循环, 第一次从右往左, 计算每个元素右边的最大值
第二次从左往右, 计算每个元素左边的最大值, 并累计可接雨水
时间复杂度O(2*n)

public int trap_better(int[] height) {
        if(height.length < 3){
            return 0;
        }

        int[] rightMax = new int[height.length];
        rightMax[height.length - 1] = 0;
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i+1], rightMax[i+1]);
        }

        int s = 0;

        int leftMax = 0;
        for (int i = 1; i < height.length-1; i++) {
            leftMax = Math.max(leftMax, height[i - 1]);

            int eachCapacity = Math.min(leftMax, rightMax[i]) - height[i];
            if (eachCapacity > 0) {
                s += eachCapacity;
            }
        }

        return s;
    }