单调栈的三个问题

一上午做了三道单调栈的问题，算是小摸了一下单调栈的套路，虽然很难想，掌握了规律还是很好做出来的！

84，柱状图中最大的矩形，hard

739，每日温度，medium

42，接雨水，hard

84，柱状图中最大的矩形，hard

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

题解

先考虑暴力解法，也就是对数组的每个高度来说，向左找、向右找到第一个比它小的高度，即可确定矩阵的宽，很容易就得到最大面积。

但这样时间复杂度比较高，每个元素都要循环两遍，为O(N²)，考虑怎么优化呢？

以空间换时间，对每个元素向后找比它小的，才能计算面积，符合【栈】先进后出的规则。用一个单调栈来记录下标（高度可以用下标来表示），这样就能很清楚的确定形成矩形的宽了。

如果当前的高度比它之前的高度（栈顶元素的高度）严格小于的时候，就可以直接确定以栈顶元素为高的矩形的面积，向左回退的时候，其实就可以当中间这些柱形不存在一样。

还有一个细节，为了确定数组两端元素的高为矩形的面积，在数组两端添加比 1 小的元素，这样就始终保证栈非空。

下面图帮助理解

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
// //暴力解
//         int res = 0;
//         for(int i = 0; i < heights.length; i++){
//             int left = i;
//             int right = i;
//             //向左找可以构成矩形的
//             while(left > 0 && heights[left - 1] >= heights[i]){
//                 left--;
//             }
//             //向右找可以构成矩形的
//             while(right < heights.length - 1 && heights[right + 1] >= heights[i]){
//                 right++;
//             }
//             int width = right - left + 1;
//             res = Math.max(res, width * heights[i]);
//         }
//         return res;
//单调栈：将数组左右两侧各加 < 1 的柱子，这样所有元素的左边都比当前柱子小，只需找到右边第一个比当前柱子小的，即可确定以当前高度为高的矩形面积（宽即为左右两边第一个比当前柱子小的两柱子之间距离，左边即为栈顶元素）
        //重构数组
        int len = heights.length;
        int[] nums = new int[len + 2];
        nums[0] = 0;
        nums[len + 1] = 0;
        for(int i = 1; i < len + 1; i++){
            nums[i] = heights[i - 1];
        }
        //单调栈中确定以数组每个元素的高度确定矩形的面积，并维护最大值res
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0; i < len + 2; i++){
            //当前高度比栈顶高度小即可确定栈顶元素的高度为高的矩形面积
            while(!stack.isEmpty() && nums[i] < nums[stack.peekLast()]){
                //栈顶元素出栈
                int h = nums[stack.removeLast()];
                //栈顶元素的高度为高的矩形面积
                res = Math.max(res, h * (i - stack.peekLast() - 1));
            }
            stack.addLast(i);
        }
        return res;
    }
}

739，每日温度，medium

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

题解

首先想到暴力解法，两层for循环，搜索每个元素后面比它大的值，就得到每个元素需要等待的天数。

此题目的是向右找到比当前索引对应的高度 高 的 第一个柱体，所以需要维护一个递减栈。

遍历数组元素，当前索引对应的高度比栈顶元素对应高度 大，即弹出栈顶并将索引差记录到结果数组。

动画演示

代码

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[T.length];
        for(int i = 0; i < T.length; i++){
            while(!stack.isEmpty() && T[i] > T[stack.peek()]){
                int idx = stack.pop();
                res[idx] = i - idx;
            }
            stack.push(i);
        }
        return res;
    }
}

42，接雨水，hard

给定 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 个单位的雨水（蓝色部分表示雨水）。

题解

依然是遍历到右面不比自己低的柱子时，会形成坑接住雨水。所以采用【单调栈】。

维护一个递减的单调栈，仍记录下标，栈中每个元素表示接雨水的【左侧柱体】。

遍历数组元素，当前元素对应高度大于栈顶元素对应高度，则能形成雨水，栈顶元素弹出，并记录其索引，去除栈中元素对应高度重复的元素（为了不重复计算）。计算雨水时，仍然采用高度*宽度，宽度 = 当前遍历索引 - 栈顶索引 - 1；高度 = 两侧柱体取最矮的 - 上面记录的弹出栈的索引对应的高度。因为以记录的柱体作为左侧柱体的雨水已经计算过了！

可以跟着甜姨的图解理解一下

代码

class Solution {
    public int trap(int[] height) {        
		if(height.length == 0 || height == null) return 0;
        int res = 0;
        int n = height.length;
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && height[i] > height[stack.peekLast()]){
                int popIdx = stack.removeLast();
                //去除高度重复的栈顶
                while(!stack.isEmpty() && height[stack.peekLast()] == height[popIdx]){
                    stack.removeLast();
                }
                //计算雨水面积
                if(!stack.isEmpty()){
                    int idx = stack.peekLast();
                    //雨水面积为 宽*高，宽是当前元素与栈顶元素的距离，高取雨水两边的较矮高度-已经计算过的高度
                    res += (i - idx - 1) * (Math.min(height[i], height[idx]) - height[popIdx]);
                }
            }
            stack.addLast(i);
        }
        return res;
    }
}

总结

这三道题都可以用单调栈来解，各自也有不同的解法。总的来说，【单调栈】以空间换时间，使暴力解法的左右两次循环变为朝一个方向循环一次。在向左。

还有一个细节，就是记录下标，而不是将元素值入栈，这是为了方便计算间隔来计算面积，写代码时要提醒自己。