专题 8：单调栈

发布日期: 2017-09-17

应该先理解暴力解法，然后画图，去理解单调栈是如何工作的。

题目描述

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

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

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

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

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

方法一：暴力解法

枚举矩形的上边界为整个边界，然后求最大值。

1、左边看一下，最多能延伸多长；小于等于它的，第 1 个元素的位置；

2、右边看一下，最多能延伸多长；大于等于它的，第 1 个元素的位置；

左右是对称的。

1、看定义，就是单调栈的经典操作。

2、和双指针的思路是一样的，首先想一下暴力怎么写。

Java 代码：

public class Solution {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 特判
        if (len == 0) {
            return 0;
        }

        int res = 0;
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = i;

            // 找左边第 1 个严格小于 heights[i] 的索引
            while (left > 0 && heights[left - 1] >= heights[i]) {
                left--;
            }
            // 找右边第 1 个严格小于 heights[i] 的索引
            while (right < len - 1 && heights[right + 1] >= heights[i]) {
                right++;
            }

            // System.out.println("左：" + left + "，右："+ right + "，高："+ heights[i]);
            int width = right - left + 1;
            res = Math.max(res, width * heights[i]);
        }
        return res;
    }
}

方法二：单调栈

注意事项：

1、画图，动态分析，栈是如何工作的；

2、遍历的时候，当前试图添加进栈的柱形高度严格小于栈顶的柱形的高度的时候，栈顶的柱形面积可以确定，所以弹出。

因为值可以确定，所以弹出；

计算面积的时候，高度是刚刚弹出的柱形的高度，宽度是柱形的左边和右边，左边是弹出以后的栈顶索引，右边就是目前视图添加进栈的索引，因此是 (i - stack.peek() - 1)；如果此时栈为空，说明，刚刚弹出的是目前看到的最小元素，它所确定的面积的宽度就是 i

3、最后不要忘记把栈清空一下。

这一步可以加上一个哨兵，因为这个栈的特点是单调不减栈，因此，哨兵元素设置为 $0$ 即可。

点击：题解链接有更详细的介绍。

不使用哨兵的写法

Java 代码：

import java.util.Stack;

public class Solution {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 特判
        if (len == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int res = 0;

        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                // top 所在的柱形的最大高度可以确定
                int top = stack.pop();
                int width;

                if (stack.isEmpty()) {
                    width = i;
                } else {
                    width = i - stack.peek() - 1;
                }

                res = Math.max(res, heights[top] * width);
            }
            stack.push(i);
        }

        // 注意：如果栈里有元素，需要清空
        while (!stack.isEmpty()) {
            // top 所在的柱形的最大高度可以确定
            int top = stack.pop();
            int width;

            if (stack.isEmpty()) {
                width = len;
            } else {
                width = len - stack.peek() - 1;
            }

            res = Math.max(res, heights[top] * width);
        }
        return res;
    }
}

使用哨兵的写法

Java 代码：

import java.util.Stack;

public class Solution {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 特判
        if (len == 0) {
            return 0;
        }

        // 最后一个 0 类似于哨兵，为了将栈中的元素全部清空
        int[] newHeights = new int[len + 1];
        System.arraycopy(heights, 0, newHeights, 0, len);
        newHeights[len] = 0;

        // 注意：为了避免编码出错，将 heights 指向新的 newHeights
        heights = newHeights;

        Stack<Integer> stack = new Stack<>();
        int res = 0;

        // 注意：for 循环里面是小于等于，即 i <= len
        for (int i = 0; i <= len; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                // top 所在的柱形的最大高度可以确定
                int top = stack.pop();
                int width;

                if (stack.isEmpty()) {
                    width = i;
                } else {
                    width = i - stack.peek() - 1;
                }

                res = Math.max(res, heights[top] * width);
            }
            stack.push(i);
        }
        return res;
    }
}

「力扣」第 84 题：柱状图中最大的矩形

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

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

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

方法一：暴力解法

这道问题的暴力解法比“接雨水”那道题要其实好想得多。

我们可以枚举以每个柱形为高度的最大矩形的面积。

具体来说就是：依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少。

为此，我们需要。

左边看一下，看最多能向左延伸多长，找到大于等于当前柱形高度的最左边元素的下标；
右边看一下，看最多能向右延伸多长；找到大于等于当前柱形高度的最右边元素的下标。

对于每一个位置，我们都这样操作，得到一个矩形面积，求出它们的最大值。

Java 代码：

public class Solution {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 特判
        if (len == 0) {
            return 0;
        }

        int res = 0;
        for (int i = 0; i < len; i++) {

            // 找左边最后 1 个大于等于 heights[i] 的下标
            int left = i;
            int curHeight = heights[i];
            while (left > 0 && heights[left - 1] >= curHeight) {
                left--;
            }

            // 找右边最后 1 个大于等于 heights[i] 的索引
            int right = i;
            while (right < len - 1 && heights[right + 1] >= curHeight) {
                right++;
            }

            int width = right - left + 1;
            res = Math.max(res, width * curHeight);
        }
        return res;
    }
}

这样写的 Python 代码是会超时的。

Python 代码：（Python 代码会超时）

from typing import List


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        size = len(heights)
        res = 0

        for i in range(size):
            left = i
            cur_height = heights[i]
            while left > 0 and heights[left - 1] >= cur_height:
                left -= 1

            right = i
            while right < size - 1 and heights[right + 1] >= cur_height:
                right += 1

            max_width = right - left + 1
            res = max(res, max_width * cur_height)
        return res

复杂度分析：

时间复杂度：$O(N^2)$；
空间复杂度：$O(1)$。

方法二：以空间换时间，用到的数据结构是栈

看到时间复杂度为 $O(N^2)$ 和空间复杂度为 $O(1)$ 的组合，那么我们是不是可以一次遍历，不需要中心扩散就能够计算出每一个高度所对应的那个最大面积矩形的面积呢？

其实很容易想到的优化的思路就是“以空间换时间”。我们需要在遍历的过程中记录一些信息。

要搞清楚这个过程，请大家一定要在纸上画图，搞清楚一些细节，这样在编码的时候就不容易出错了。

记录什么信息呢？记录高度是不是可以呢？其实是不够的，因为计算矩形还需要计算宽度，很容易知道宽度是有下标确定的，记录了下标其实对应的高度就可以直接从输入数组中得出。

我们就拿示例的数组 [2, 1, 5, 6, 2, 3] 为例：

一开始看到的柱形高度为 2 ，这个时候以这个 2 为高度的最大面积的矩形是不能确定下来的，为此我们需要继续向右遍历；
然后遍历到高度为 1 的柱形，这个时候以这个柱形为高度的矩形的最大面积还是不知道的，但是它之前的以 2 为高度的最大面积的矩形是可以确定的，这是因为这个 1 比 2 小，因为这个 1 卡在了这里 2 不能再向右边扩展了。我们计算一下以 2 为高度的最大矩形的面积，就是 2；这个时候，求解这个问题的思路其实已经慢慢展开了；
遍历到高度为 5 的柱形，同样的以当前看到柱形为高度的矩形的最大面积也是不知道的，因为我们还要看右边高度的情况。那么它的左右有没有可以确定的柱形呢？没有，这是因为 5 比 1 大，我们看后面马上就出现了 6，不管是 1 这个柱形还是 5 这个柱形，都还可以向右边扩展；
接下来，遍历到高度为 6 的柱形，同样的，以柱形 1、5、6 为高度的最大矩形面积还是不能确定下来；
再接下来，遍历到高度为 2 的柱形，唉，发现了一件很神奇的事情，柱形 6对应的最大面积的矩形的宽度可以确定下来，它就是夹在 5 和 2 之间的距离，它的高度是 1；
并且柱形 5 对应的最大面积的矩形的宽度也可以确定下来，它是夹在柱形 1 和柱形 2 之间的距离；

我们发现了，只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边。

这个现象就提示我们，我们在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。

这个时候，还需要考虑的一个细节是，我在确定一个柱形的面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小。

那如果是左边的高度和自己相等怎么办呢？我们想一想，我们之前是只要比当前严格小，我们才可以确定一些柱形的最大宽度。只要是大于或者等于之前看到的那一个柱形的高度的时候，我们其实都不能确定。

因此我们确定当前柱形对应的宽度的左边界的时候，往回头看的时候，一定要找到第一个严格小于我们要确定的那个柱形的高度的下标。这个时候中间那些相等的柱形其实就可以当做不存在一样。因为它对应的最大矩形和它对应的最大矩形其实是一样的。

说到这里，其实我们的思路已经慢慢清晰了。

我们在遍历的时候，需要记录的是下标，如果当前的高度比它之前的高度严格小于的时候，就可以直接确定之前的那个高的柱形的最大矩形的面积，为了确定这个最大矩形的左边界，我们还要找到第一个严格小于它的高度的矩形，向左回退的时候，其实就可以当中间这些柱形不存在一样。

这是因为我们就是想确定 6 的宽度，6 的宽度确定完了，其实我们就不需要它了，这个 5 的高度和这个 5 的高度确定完了，我们也不需要它了，因此我们就相当于只在一个数据结构的一侧进行操作，这个数据结构就是栈，它恰好符合我们这个问题后进先出的特点。

当确定了一个柱形的高度的时候，我们就将它从栈顶移出，所有的柱形在栈中进栈一次，出栈一次，一开始栈为空，最后也一定要让栈为空，表示这个高度数组里所有的元素都考虑完了。

Java 代码：

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution6 {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }

        if (len == 1) {
            return heights[0];
        }

        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>(len);
        for (int i = 0; i < len; i++) {
            // 这个 while 很关键
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
                    stack.pollLast();
                }

                int curWidth;
                if (stack.isEmpty()) {
                    curWidth = i;
                } else {
                    curWidth = i - stack.peekLast() - 1;
                }

                // System.out.println("curIndex = " + curIndex + " " + curHeight * curWidth);
                res = Math.max(res, curHeight * curWidth);
            }
            stack.add(i);
        }

        while (!stack.isEmpty()) {
            int curHeight = heights[stack.pollLast()];
            while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
                stack.pollLast();
            }
            int curWidth;
            if (stack.isEmpty()) {
                curWidth = len;
            } else {
                curWidth = len - stack.peekLast() - 1;
            }
            res = Math.max(res, curHeight * curWidth);
        }
        return res;
    }


    public static void main(String[] args) {
        int[] heights = new int[]{2, 1, 5, 6, 2, 3};
        Solution6 solution6 = new Solution6();
        int res = solution6.largestRectangleArea(heights);
        System.out.println(res);
    }
}

Java 代码：加了哨兵的写法。

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }

        if (len == 1) {
            return heights[0];
        }

        int res = 0;

        int[] newHeights = new int[len + 2];
        newHeights[0] = 0;
        System.arraycopy(heights, 0, newHeights, 1, len);
        newHeights[len + 1] = 0;
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>(len);
        for (int i = 0; i < len; i++) {

            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];

                while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
                    stack.pollLast();
                }

                int curWidth = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.add(i);
        }
        return res;
    }
}

Java 代码：

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int res = 0;

        int[] newHeights = new int[len + 2];
        newHeights[0] = 0;
        System.arraycopy(heights, 0, newHeights, 1, len);
        newHeights[len + 1] = 0;
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>(len);
        for (int i = 0; i < len; i++) {

            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.add(i);
        }
        return res;
    }
}