柱状图中最大的矩形

原题：84. Largest Rectangle in Histogram

题目描述：

给定\(n\)个非负整数，用来表示柱状图中每个柱子的高度。每个柱子相邻且宽度为1。
求这个柱状图中能容纳的最大矩形的面积。

思路：

对于一个柱状图中的最大矩形，我们可以观察出如下性质：

1. 矩形的高必等于某个柱子的高度，也就是矩形的上边与某个柱子的上边在同一条直线上。
   证明：假设上述不成立。那对于每个柱子，它们的高都比这个最大矩形的高至少大1。因此我们可以增加这个矩形的高，得到一个更大的矩形，并且这个矩形还在柱状图中。因此这个矩形不是最大的矩形，得出悖论。因此此条性质成立。
2. 矩形的左边柱子的高度小于矩形高度，矩形的右边柱子的高度小于矩形的高度。
   证明：显而易见，如果左右两边的柱子高度大于等于矩形的高度，那么就可以向左右延伸矩阵，得到一个更大的矩阵。

根据上面两个性质，我们可以得出一个求最大矩阵的算法：

算法：

对于每一个柱子\(i\)，如果我们知道它左边和右边第一个比它矮的柱子的位置\(left,\ right\)，我们就可以计算出以这个柱子\(i\)为顶边的最大矩形，其面积为\((right-left-1)\times height[i]\)。
对于每个柱子都进行上述计算，取其中的最大值，即为整个柱状图中的最大矩形。

那如何求每个柱子左右两边第一个比它矮的柱子位置呢？可以拆解为两个问题：1. 找到每个柱子右边第一个比它矮的柱子的位置。2. 找到每个柱子左边第一个比它矮的柱子的位置。
像这样具有单调性的题目，应该使用单调栈解决。下面演示单调递增栈的细节。

单调栈(单调递增栈)

记一个数组\(right\)，大小为\(n\)即总元素的个数。用来记录每个\(index\)对应的右边的第一个小于\(height[index]\)的元素的\(index'\)。我们将其初始化为\(n\)，即默认右边第一个小于\(height[index]\)的元素的位置为\(n\)。
维护一个栈(存的是元素的index)，对于每一个新元素\(a\)，如果大于等于栈顶元素，直接把其index push进栈；如果比栈顶元素小，把栈顶元素对应的\(right[i]\)设为\(a\)的\(index\)，再对栈进行pop操作。如此反复直到\(a\)大于等于栈顶元素，再把其index push进栈。循环完了，如果栈中还剩下元素。这些元素的右边没有比它们小的元素，于是就默认为\(n\)了。

通过上述过程我们可以得到每个柱子右边第一个比它矮的柱子的位置。同理可以得到每个柱子左边第一个比它矮的柱子的位置。但是通过观察可以发现：每个元素的index在被push进入栈的时候其左边界就可以“确定了”：为栈顶的index。解释如下：

如果栈中没两个相邻的元素的高不同，我们在进行push进栈的时候，栈顶的元素的值已经小于我们将push进去元素的值了。因此每个元素在被push的时候左边界就确定了，为栈顶的值。

如果栈中有高相同的元素相邻，如\(a,b:height[a]=height[b],a<=b\)。采用上述方法的，\(b\)的左边界值就不准确了，因为其左边界值被设置为\(a\)，但其实\(height[a]=height[b]\)，\(b\)的真实左边界值其实应该比\(a\)小。以柱子\(b\)为顶边的矩形的面积就不是最大的，因为这个矩形还能向左延伸。那怎么办呢？

其实这样的不准确并不影响求以\(a\)或\(b\)为上边的矩形的面积。既然\(height[a]=height[b]\)，并且它们在栈中相邻，说明它们中间没有比它们小的值。对于元素\(a\)，其左边界是准确的，即\(height[left[a]]<height[a]\)。并且以柱子\(a\)为顶边的矩形包含了以柱子\(b\)为顶边的矩形。所以即使栈中在\(a\)上面还有很多元素，其柱子高度等于柱\(a\)的高度，并且它们的左边界都不准确。只要同高的最左元素\(a\)的左边界正确就能确定它们包围的矩形的最大面积。

所以我们可以在求右边界的时候就可以确定左边界的位置。

详细代码如下：Java

class p84 {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length, maxSize = 0;
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        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);
        }
        for (int i = 0; i < n; i++) {
            maxSize = Math.max(maxSize, (right[i] - left[i] - 1) * heights[i]);
        }
        return maxSize;
    }
}

复杂度分析：

空间复杂度：使用两个数组存左右边界，复杂度为\(O(n)\)。
时间复杂度：遍历每个元素为\(n\)，在遍历中进行pop、push等操作，但是pop和push的总操作量小于\(O(2n)\)，最后遍历计算最大面积\(O(n)\)。因此总时间复杂度为\(O(n)\)。