柱状图中最大的矩形

1.题目内容

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

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

示例 1:

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

示例 2：

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

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

2.解法

（3）单调栈

思路及算法

我们归纳一下枚举「高」的方法：

• 首先我们枚举某一根柱子 i 作为高 h=heights[i]；
• 随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 h。换句话说，我们需要找到左右两侧最近的高度小于 h 的柱子，这样这两根柱子之间（不包括其本身）的所有柱子高度均不小于 h，并且就是 iii 能够扩展到的最远范围。

那么我们先来看看如何求出一根柱子的左侧且最近的小于其高度的柱子。除了根据「前言」部分暴力地进行枚举之外，我们可以通过如下的一个结论来深入地进行思考：

对于两根柱子 j0 以及 j1，如果 j0<j1并且 heights[j0]≥heights[j1]，那么对于任意的在它们之后出现的柱子 i（j1<i） 一定不会是 i 左侧且最近的小于其高度的柱子。

换句话说，如果有两根柱子 j0 和 j1，其中 j0 在 j1 的左侧，并且 j0 的高度大于等于 j1，那么在后面的柱子 i 向左找小于其高度的柱子时，j1 会「挡住」j0，j0 就不会作为答案了。

这样以来，我们可以对数组从左向右进行遍历，同时维护一个「可能作为答案」的数据结构，其中按照从小到大的顺序存放了一些 j 值。根据上面的结论，如果我们存放了 j0,j1,⋯ ,js，那么一定有 height[j0]<height[j1]<⋯<height[js]，因为如果有两个相邻的 j 值对应的高度不满足 < 关系，那么后者会「挡住」前者，前者就不可能作为答案了。

当我们枚举到第 i 根柱子时，我们的数据结构中存放了 j0,j1,⋯ ,js，如果第 iii 根柱子左侧且最近的小于其高度的柱子为 ji，那么必然有height[j0]<height[j1]<⋯<height[ji]<height[i]≤height[ji+1]<⋯<height[js] 这样我们就可以使用二分查找的方法找到 i 对应的 ji，但真的需要吗？当我们枚举到 i+1 时，原来的 i 也变成了 j值，因此 i 会被放入数据结构。由于所有在数据结构中的 j 值均小于 i，那么所有高度大于等于 height[i] 的 j 都不会作为答案，需要从数据结构中移除。而我们发现，这些被移除的 j 值恰好就是ji+1,⋯ ,js。

这样我们在枚举到第 i 根柱子的时候，就可以先把所有高度大于等于 height[i] 的 j 值全部移除，剩下的 j值中高度最高的即为答案。在这之后，我们将 i 放入数据结构中，开始接下来的枚举。此时，我们需要使用的数据结构也就呼之欲出了，它就是栈。

• 栈中存放了 j 值。从栈底到栈顶，j 的值严格单调递增，同时对应的高度值也严格单调递增；

• 当我们枚举到第 i 根柱子时，我们从栈顶不断地移除 height[j]≥height[i] 的 j 值。在移除完毕后，栈顶的 j 值就一定满足 height[j]<height[i]，此时 j 就是 i 左侧且最近的小于其高度的柱子。

  • 这里会有一种特殊情况。如果我们移除了栈中所有的 j 值，那就说明 i 左侧所有柱子的高度都大于 height[i]，那么我们可以认为 i 左侧且最近的小于其高度的柱子在位置 j=−1，它是一根「虚拟」的、高度无限低的柱子。这样的定义不会对我们的答案产生任何的影响，我们也称这根「虚拟」的柱子为「哨兵」。

• 我们再将 i 放入栈顶。

栈中存放的元素具有单调性，这就是经典的数据结构「单调栈」了。

代码

//C++
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);
        
        stack<int> mono_stack;
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
            mono_stack.push(i);
        }

        mono_stack = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.empty() ? n : mono_stack.top());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

//Java
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(N)。

（2）单调栈+常数优化

思路及算法

在方法一中，我们首先从左往右对数组进行遍历，借助单调栈求出了每根柱子的左边界，随后从右往左对数组进行遍历，借助单调栈求出了每根柱子的右边界。那么我们是否可以只遍历一次就求出答案呢？

答案是可以的。在方法一中，我们在对位置 i 进行入栈操作时，确定了它的左边界。从直觉上来说，与之对应的我们在对位置 i 进行出栈操作时可以确定它的右边界！仔细想一想，这确实是对的。当位置 i 被弹出栈时，说明此时遍历到的位置 i0 的高度小于等于 height[i]，并且在 i0 与 i 之间没有其他高度小于等于 height[i] 的柱子。这是因为，如果在 i 和 i0之间还有其它位置的高度小于等于 height[i] 的，那么在遍历到那个位置的时候，i 应该已经被弹出栈了。所以位置 i0 就是位置 i 的右边界。

等等，我们需要的是「一根柱子的左侧且最近的小于其高度的柱子」，但这里我们求的是小于等于，那么会造成什么影响呢？答案是：我们确实无法求出正确的右边界，但对最终的答案没有任何影响。这是因为在答案对应的矩形中，如果有若干个柱子的高度都等于矩形的高度，那么最右侧的那根柱子是可以求出正确的右边界的，而我们没有对求出左边界的算法进行任何改动，因此最终的答案还是可以从最右侧的与矩形高度相同的柱子求得的。读者可以仔细思考一下这一步。

在遍历结束后，栈中仍然有一些位置，这些位置对应的右边界就是位置为 n 的「哨兵」。我们可以将它们依次出栈并更新右边界，也可以在初始化右边界数组时就将所有的元素的值置为 n。

代码

//C++
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n, n);
        
        stack<int> mono_stack;
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                right[mono_stack.top()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

//Java
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(N)。