题目链接
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入： heights = [2,1,5,6,2,3]
输出： 10
解释： 最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
1 <= heights.length <=105-
方法一：暴力法
从当前位置左右遍历，到小于当前位置的高度停止。
class Solution {public int largestRectangleArea(int[] heights) {int ans = 0;int left, right;for(int i = 0; i < heights.length; ++i){left = i;while(left >=0 && heights[left] >= heights[i] ){--left;}right = i;while(right < heights.length && heights[right] >= heights[i]){++right;}ans = Math.max(ans, heights[i] * (right - left - 1));}return ans;}}
时间复杂度 O(n^2)
- 空间复杂度 O(n)
方法二：单调栈
要搞清楚这个过程，请大家一定要在纸上画图，搞清楚一些细节，这样在编码的时候就不容易出错了。
记录什么信息呢？记录高度是不是可以呢？其实是不够的，因为计算矩形还需要计算宽度，很容易知道宽度是由下标确定的，记录了下标其实对应的高度就可以直接从输入数组中得出，因此，应该记录的是下标。
我们就拿示例的数组 [2, 1, 5, 6, 2, 3] 为例：
1、一开始看到的柱形高度为 2 ，这个时候以这个 2 为高度的最大面积的矩形还不能确定，我们需要继续向右遍历，如下图。
2、然后看到到高度为 1 的柱形，这个时候以这个柱形为高度的矩形的最大面积还是不知道的。但是它之前的以 2 为高度的最大面积的矩形是可以确定的，这是因为这个 1 比 2 小 ，因为这个 1 卡在了这里 2 不能再向右边扩展了，如下图。
我们计算一下以 2 为高度的最大矩形的面积是 2。其实这个时候，求解这个问题的思路其实已经慢慢打开了。如果已经确定了一个柱形的高度，我们可以无视它，将它以虚框表示，如下图。
3、遍历到高度为 5 的柱形，同样的以当前看到柱形为高度的矩形的最大面积也是不知道的，因为我们还要看右边高度的情况。那么它的左右有没有可以确定的柱形呢？没有，这是因为 5 比 1 大，我们看后面马上就出现了 6，不管是 1 这个柱形还是 5 这个柱形，都还可以向右边扩展；
4、接下来，遍历到高度为 6 的柱形，同样的，以柱形 1、5、6 为高度的最大矩形面积还是不能确定下来；
5、再接下来，遍历到高度为 2 的柱形。
发现了一件很神奇的事情，高度为 6 的柱形对应的最大矩形的面积的宽度可以确定下来，它就是夹在高度为 5 的柱形和高度为 2 的柱形之间的距离，它的高度是 6，宽度是 1。
将可以确定的柱形设置为虚线。
接下来柱形 5 对应的最大面积的矩形的宽度也可以确定下来，它是夹在高度为 1 和高度为 2 的两个柱形之间的距离；
确定好以后，我们将它标成虚线。
我们发现了，只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边。 这个现象告诉我们，在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。
这个时候，还需要考虑的一个细节是，在确定一个柱形的面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小。
那如果是左边的高度和自己相等怎么办呢？我们想一想，我们之前是只要比当前严格小，我们才可以确定一些柱形的最大宽度。只要是大于或者等于之前看到的那一个柱形的高度的时候，我们其实都不能确定。
因此我们确定当前柱形对应的宽度的左边界的时候，往回头看的时候，一定要找到第一个严格小于我们要确定的那个柱形的高度的下标。这个时候 中间那些相等的柱形其实就可以当做不存在一样。因为它对应的最大矩形和它对应的最大矩形其实是一样的。
说到这里，其实我们的思路已经慢慢清晰了。
我们在遍历的时候，需要记录的是下标，如果当前的高度比它之前的高度严格小于的时候，就可以直接确定之前的那个高的柱形的最大矩形的面积，为了确定这个最大矩形的左边界，我们还要找到第一个严格小于它的高度的矩形，向左回退的时候，其实就可以当中间这些柱形不存在一样。
这是因为我们就是想确定 6 的宽度，6 的宽度确定完了，其实我们就不需要它了，这个 5 的高度和这个 5 的高度确定完了，我们也不需要它了。
我们在缓存数据的时候，是从左向右缓存的，我们计算出一个结果的顺序是从右向左的，并且计算完成以后我们就不再需要了，符合后进先出的特点。因此，我们需要的这个作为缓存的数据结构就是栈。
当确定了一个柱形的高度的时候，我们就将它从栈顶移出，所有的柱形在栈中进栈一次，出栈一次，一开始栈为空，最后也一定要让栈为空，表示这个高度数组里所有的元素都考虑完了。
6、最后遍历到最后一个柱形，即高度为 3 的柱形。
（一次遍历完成以后。接下来考虑栈里的元素全部出栈。）
接下来我们就要依次考虑还在栈里的柱形的高度。和刚才的方法一样，只不过这个时候右边没有比它高度还小的柱形了，这个时候计算宽度应该假设最右边还有一个下标为 len （这里等于 6） 的高度为 0 （或者 0.5，只要比 1 小）的柱形。
7、下标为 5 ，即高度为 3 的柱形，左边的下标是 4 ，右边的下标是 6 ，因此宽度是 6 - 4 - 1 = 1（两边都不算，只算中间的距离，所以减 1）；算完以后，将它标为虚线。
8、下标为 4 ，高度为 2 的柱形，左边的下标是 1 ，右边的下标是 6 ，因此宽度是 6 - 1 - 1 = 4；算完以后，将它标为虚线。
9、最后看下标为 1，高度为 1 的矩形，它的左边和右边其实都没有元素了，它就是整个柱形数组里高度最低的柱形，计算它的宽度，就是整个柱形数组的长度。
到此为止，所有的柱形高度对应的最大矩形的面积就都计算出来了。
这个算法经过一次遍历，在每一次计算最大宽度的时候，没有去遍历，而是使用了栈里存放的下标信息，以 O(1) 的时间复杂度计算最大宽度。
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length;
int ans = 0;
Deque<Integer> stack = new LinkedList<>();
for(int i = 0; i < len; ++i){
while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
int height = heights[stack.pop()];
while(!stack.isEmpty() && heights[stack.peek()] == height){
stack.pop();
}
int width;
if(stack.isEmpty()){
width = i;
}else{
width = i - stack.peek() - 1;
}
ans = Math.max(ans, height * width);
}
stack.push(i);
}
while(!stack.isEmpty()){
int height = heights[stack.pop()];
while(!stack.isEmpty() && heights[stack.peek()] == height){
stack.pop();
}
int width;
if(stack.isEmpty()){
width = len;
}else{
width = len - stack.peek() - 1;
}
ans = Math.max(ans, height * width);
}
return ans;
}
}
- 时间复杂度 O(n)
- 空间复杂度 O(n)
以上参考代码 2 需要考虑两种特殊的情况：
- 弹栈的时候，栈为空；
- 遍历完成以后，栈中还有元素；
为此可以我们可以在输入数组的两端加上两个高度为 0 （或者是 0.5，只要比 1 严格小都行）的柱形，可以回避上面这两种分类讨论。
这两个站在两边的柱形有一个很形象的名词，叫做哨兵（Sentinel）。
有了这两个柱形：
- 左边的柱形（第 1 个柱形）由于它一定比输入数组里任何一个元素小，它肯定不会出栈，因此栈一定不会为空；
- 右边的柱形（第 2 个柱形）也正是因为它一定比输入数组里任何一个元素小，它会让所有输入数组里的元素出栈（第 1 个哨兵元素除外）。
这里栈对应到高度，呈单调增加不减的形态，因此称为单调栈（Monotone Stack）。它是暴力解法的优化，计算每个柱形的高度对应的最大矩形的顺序由出栈顺序决定。
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length;
int ans = 0;
Deque<Integer> stack = new LinkedList<>();
int[] newHeights = new int[len + 2];
System.arraycopy(heights, 0, newHeights, 1, len);
newHeights[0] = 0;
newHeights[len+1] = 0;
heights = newHeights;
// 先放入哨兵，在循环里就不用做非空判断
stack.push(0);
for(int i = 1; i <= len+1; ++i){
while(heights[stack.peek()] > heights[i]){
int height = heights[stack.pop()];
while(heights[stack.peek()] == height){
stack.pop();
}
int width = i - stack.peek() - 1;
ans = Math.max(ans, width * height);
}
stack.push(i);
}
return ans;
}
}
若有收获，就点个赞吧
0 人点赞
