给定(n)个非负整数，用来表示柱状图中每个柱子的高度。每个柱子相邻且宽度为1。
求这个柱状图中能容纳的最大矩形的面积。
对于一个柱状图中的最大矩形，我们可以观察出如下性质：
根据上面两个性质，我们可以得出一个求最大矩阵的算法：
对于每一个柱子(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
其实这样的不准确并不影响求以(a)或(b)为上边的矩形的面积。既然(height[a]=height[b])，并且它们在栈中相邻，说明它们中间没有比它们小的值。对于元素(a)，其左边界是准确的，即(height[left[a]]
所以我们可以在求右边界的时候就可以确定左边界的位置。
详细代码如下：Java
class p84 {
public int largestRectangleArea(int[] heights) {
int n = heights.length, maxSize = 0;
Deque mono_stack = new ArrayDeque();
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))。
Original: https://www.cnblogs.com/liuzhch1/p/16124393.html
Author: liuzhch1
Title: LeetCode 84.柱状图中最大的矩形 | 单调栈的使用 | 解题思路及算法 Java
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/620694/
转载文章受原作者版权保护。转载请注明原作者出处！