LeetCode-84-柱状图中最大的矩阵
1. 题目描述
给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
1 | 输入: [2,1,5,6,2,3] |
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为[2,1,5,6,2,3]。
2. 思路
2.1暴力搜索
暴力搜索的思路就是，对于每一个bar，我们都去寻找以该bar为高度，且宽度尽量最宽的矩形，也就是以当前bar为中心，设置两个指针left、right，让它们各自尽可能移到更远的地方去。
这个实现也很简单，每个bar都要移动双指针，因此时间复杂度为$O(N^2)$,空间复杂度则是$O(1)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// 暴力搜索
private int bruteforce(int[] heights)
{
int maxArea=0;
// 以heights[i]为高度的矩形
for(int i=0;i<heights.length;i++)
{
int left=i-1,right=i+1;
while(left>=0 && heights[left]>=heights[i])
left--;
while(right<heights.length && heights[right]>=heights[i])
right++;
maxArea=Math.max(maxArea,heights[i]*(right-left-1));
}
return maxArea;
}
2.2单调栈
显然，暴力搜索不是最优解，此题最优策略是用单调栈来解。以[2,1,5,6,2,3]为例子来讲解。
一开始，我们看到一个2，这个时候呢，以2为高度的矩形的最大面积无法确定，因为我们不知道最大的宽度是多少，于是继续向右遍历，如下图。
然后遍历到高度为1的高度，和之前高度为2的情况一样，我们此时无法确定以1位高度的矩形的最大面积，因为不知道高度为1的矩形宽度具体为多少嘛！但是，以2为高度的最大矩形是可以确定的，这是因为1比2小，1把2卡住了，使得高度为2的矩形不能再向右边扩展了，于是高度为2的矩形最大面积为2，如下图。
接下来，5和6依次到来，也很前面分析类似，我们无法知道高度为5和高度为6的最大矩形，如下图。
然后，2来了，于是前面高度比2大的矩形的最大面积全可以确定下来。高度为6的矩形的最大面积就是6乘以高度，高度是多少呢？对，就是高度为5和高度为2的bar之间的距离（即1），所以以6位高度的最大矩形面积为6。同理，可知高度为5的最大矩形面积。但是！高度为1的矩形面积还是不能确定！于是继续重复上述的过程，直到最后3来了，如下图。
这个时候，再也没有bar到来了，算法就这样停止在了这里。怎么办呢？我们可以人为添加一个比任何高度都小的“哨兵”，这里不妨设置成0。然后0到了，前面未确定最大面积的矩形现在都可以确定了，如下图。
最后，为了避免弹栈的时候栈为空，不妨在原始bar的最左段也添加一个“哨兵”，从而最后栈中肯定只会剩下2个哨兵。
具体细节请参阅weiwei的图解，上面的图也是weiwei画的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution {
public int largestRectangleArea(int[] heights) {
// 边界情况
if(heights.length==0)
return 0;
if(heights.length==1)
return heights[0];
return increasingStack(heights);
}
// 单调栈法
private int increasingStack(int[] heights) {
int maxArea = 0;
// 先在原数组的左右两边都加一个值为0的哨兵
int[] newHeights = new int[heights.length + 2];
newHeights[0] = 0;
newHeights[newHeights.length - 1] = 0;
for (int i = 0; i < heights.length; i++)
newHeights[i + 1] = heights[i];
// 栈中存储的是下标
Stack<Integer> s = new Stack<>();
for (int i = 0; i < newHeights.length; i++) {
while (!s.isEmpty() && newHeights[s.peek()] > newHeights[i]) {
int h = newHeights[s.pop()];
int idx = s.peek() ;
maxArea = Math.max(maxArea, h * (i - idx-1));
}
s.push(i);
}
return maxArea;
}
}
3.类似题
- LeetCode 85-最大矩形
给定一个仅包含0和1的二维二进制矩阵，找出只包含1的最大矩形，并返回其面积。
示例1
2
3
4
5
6
7
8输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
乍一看，好像和84题没什么关系，但是仔细分析一下，我们可以发现这样的规律：
对于矩阵中的第一行，["1","0","1","0","0"],，我们完全可以看做是一个histogram，其中有两个bar高度为1，另外3个高度为0。
再接着看第二行，我们把第二行和第一行“拼接”起来，["1","0","1","0","0"]拼接["1","0","1","1","1"]的结果是["2","0","2","1","1"]。这不是就又是一个histogram吗？然后后面的昂也这样做，每一行都求的一个最大值，最终的结果就是全局最优解了。详细参阅wallcwr提供的题解,这样一来，时间复杂度为$O(row*col)$，空间复杂度为$O(col)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length ==0 || matrix[0].length==0)
return 0;
int res=0;
// 每一行组成的柱状图
int[] histogram= new int[matrix[0].length];
for(int i =0;i<matrix.length;i++)
{
for(int j=0;j<matrix[i].length;j++)
{
histogram[j]= matrix[i][j]=='1'? histogram[j]+1:0;
}
// 以当前行形成的柱状图来求最大矩形面积
res=Math.max(res,increasingStack(histogram));
}
return res;
}
// Leetcode 第 84 题，求柱状图中最大矩形,单调栈法
private int increasingStack(int[] heights)
{
int maxArea=0;
// 先在原数组的左右两边都加一个值为0的哨兵
int[] newHeights = new int[heights.length + 2];
newHeights[0] = 0;
newHeights[newHeights.length - 1] = 0;
for (int i = 0; i < heights.length; i++)
newHeights[i + 1] = heights[i];
Stack<Integer> s= new Stack<>();
for(int i=0;i<newHeights.length;i++)
{
while(!s.isEmpty() && newHeights[s.peek()]> newHeights[i])
{
int h=newHeights[s.pop()];
int idx=s.peek();
maxArea=Math.max(maxArea,h*(i-idx-1));
}
s.push(i);
}
return maxArea;
}
}
