LeetCode.084.Largest Rectangle in Histogram 柱状图中最大的矩形

题目描述

84 Largest Rectangle in Histogram
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

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

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

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

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

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

---

相似题目

LeetCode.739.Daily Temperatures 每日温度
LeetCode.042.Trapping Rain Water 接雨水
LeetCode.084.Largest Rectangle in Histogram 柱状图中最大的矩形

LeetCode.011.Container With Most Water 盛最多水的容器

---

解题过程

这道题是典型的单调栈应用，但暴力搜索法也是要了解一下的，就像任何可优化的题目一样，我们要先知道暴力搜索如何做，再通过对暴力方法的优化来得到最优解。

暴力枚举O(n^2)

暴力搜索可通过枚举最大矩形的高度和宽度两个变量来进行：
1、枚举宽度，区间 [i,j] 决定了一个矩形的宽度，我们每次固定左边界 i，然后 O(n) 枚举右边界 j，得到一个矩形宽度 [i,j]，高度为此宽度内所有单个矩形的高度最小值，最小值可以在枚举矩形右边界的过程中获得，所以总的时间复杂度为 O(n^2)
2、枚举高度，以每个 heights[i] 为矩形的高度，则矩形的宽度为 i 分别向左右扩展到第一个高度小于 heights[i] 的左右边界。总的时间复杂度也是 O(n^2)

单调递增栈O(n)

单调栈 方法是从 枚举矩形高度 优化得来的，在枚举高度的暴力解法中，我们每次都需要 O(n) 来向左/右扩展找到第一个高度小于 heights[i] 的左/右边界值，那么我们有什么方法可以在 O(1) 时间复杂度内得到这个信息呢？

我们维护一个单调递增栈，栈内存放每个元素的下标，遇到比栈顶高度大的，直接将其下标入栈。
遇到比栈顶高度小的，我们就要开始计算并更新最大面积 max 了，依次弹出栈顶元素，直到栈顶下标对应的高度比当前高度小，对于每个栈顶下标 peekIndex，我们要计算高度为 heights[peekIndex] 的矩形的面积，并比较决定是否更新 max 值。
对应的矩形高度自然就是 heights[peekIndex]
但宽度是多少呢？
还是暴力枚举矩形高度的思路，当然是左右第一个比 heights[peekIndex] 小的矩形下标 left 和 right 组成的区间 right - left，但是这次这个信息我们可以 O(1) 直接获得，左边界 left 就是弹出栈顶 peekIndex 后的新栈顶 monoStack.peek()（如果栈为空则是 0），右边界 right 就是当前元素下标 i

矩形最大面积问题中，我们需要找到每个高度左右第一个比他小的位置下标作为左右边界，所以这个问题需要在遇到递增到递减的转折点时触发计算，所以维护一个单调递增栈，当前元素比栈顶大时入栈，比栈顶小时就遇到了右侧比栈顶小的边界，也就是递增到递减的转折点，此时栈顶的下一个元素就是左侧边界。

单调栈应用中会遇到一个问题，就是假如使用单调递增栈且原数组中元素本身就是完全单调递增的，就没有触发计算的时机，这时可以使用一个单调栈问题中经常用到的技巧，我们在原数组最后补一个虚拟的不可能在数组中存在的最小/大值，最后将其压入栈中，以便触发计算。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV202005 {
    public int largestRectangleArea(int[] heights) {
        if (null == heights || heights.length < 1) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }
        int max = 0;
        // 单调递增栈
        Deque<Integer> monoStack = new LinkedList<>();
        for (int i = 0; i <= heights.length; i++) {
            // 当前下标和值
            int curIndex, curValue;
            if (i == heights.length) {
                // 为了完成计算，数组遍历结束后向单调栈中压入一个原数组中不存在的全局最小虚拟值，下标为 heights.length，值为 -1
                curIndex = heights.length;
                curValue = -1;
            } else {
                curIndex = i;
                curValue = heights[i];
            }
            // 当栈非空，且当前值比栈顶小时，依次弹出栈中比当前值大的元素，并更新最大面积
            while (!monoStack.isEmpty() && heights[monoStack.peek()] > curValue) {
                // 栈顶下标对应的值，即矩形的高度
                int height = heights[monoStack.pop()];
                // 矩形的宽度
                int width = !monoStack.isEmpty() ? curIndex - monoStack.peek() - 1 : curIndex;
                max = Math.max(max, height * width);
            }
            // 当前值比栈顶大，或者已弹出栈中比当前值大的元素后，当前元素下标入栈
            monoStack.push(curIndex);
        }
        return max;
    }
}

---

GitHub代码

lgorithms/leetcode/leetcode/_084_LargestRectangleInHistogram.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_084_LargestRectangleInHistogram.java

---