Largest Rectangle in Histogram
Largest Rectangle in Histogram解析
题目
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
先来看一个例子
height的内容是 [5,6,7,8,3],特点是除了最后一个,前面全部保持递增,且最后一个立柱的高度小于前面所有立柱高度。对于
这种特点的柱状图,如果使用上面所说的“挨个使用每一个柱状图的高度作为矩形的高度,求面积”的方法,还需要用嵌套循环吗?
我们知道除了最后一个,从第一个到倒数第二个立柱的高度都在升高,那么如果挨个使用每一个柱的高度作为矩形的
高度,那么依次能得到的矩形的宽度就可以直接算出来:使用5作为高度可以使用前四个立柱组成 $4\times5$的矩形,高度6可以
组成$3\times6$的矩形… 因此只需要遍历一次,选出最大面积即可。对于这种类型的柱状图,最大矩形面积的时间复杂度是O(n)。我们将这种特点的柱状图称为“波峰图”。
从而算法设计步骤:
(1) 在height尾部添加一个0,也就是一个高度为0的立柱。作用是在最后也能凑成上面提的那种“波峰图”。
(2) 定义了一个stack,然后遍历时如果height[i] 大于stack.top(),进栈。反之,出栈直到栈顶元素小于height[i]。
由于出栈的这些元素高度都是递增的,我们可以求出这些立柱中所围成的最大矩形。更妙的是,由于这些被弹出的立柱处于“波峰”之上(比如弹出i 到 i+k,那么所有这些立柱的高度都高于 i-1和 i+k+1的高度),因此,如果我们使用之前所提的“左右延伸找立
柱”的思路解,以这些立柱的高度作为整个矩形的高度时,左右延伸出的矩形所包含的立柱不会超出这段“波峰”,因为波峰外的立柱
高度都比他们低。“波峰图”其实就是求解最大矩形的“孤岛”,它不会干扰到外部。
(3) 由于比height[i]大的元素都出完了,height[i]又比栈顶元素大了,因此再次进栈。如此往复,直到遍历到最后那个高度为0的柱,触发最后的弹出以及最后一次面积的计算,此后stack为空。
(4) 返回面积最大值。
栈中存的不是高度,而是height的索引,这样做的好处是不会影响宽度的计算,索引值相减 = 宽度。
但是对于面积的计算,还需要再多少几句
矩形的面积=高*宽。
我们的发现,在这个分支情况下,我们已经知道高为2了,那么宽度如何求呢?
通过观察,我们发现矩形的左边沿是左边第一个高比2小的柱子,右边沿是右边第一个高比2小的柱子(将高为3的柱子的右面看作还
有一个高为0的柱子)如此它的宽度是$6 -(1+1)=4$
如何寻找柱子的左右边
我们已经说了,左边沿是左边第一小与本柱子高的柱子的右边,右边沿也是同理。
这正好可以用单调栈。
当第i个柱子进栈时,如果栈顶柱子(此处记作柱子A)的高度低于或等于第i个柱子,则第i个柱子进栈;
如果高于第i个柱子,则出栈,并计算以柱子A为高的矩形最大面积。
- 高度:就是柱子A的高度
- 右边沿:正好是i(由于单调栈的性质,第i个柱子就是右边第一个矮于A的柱子)
- 左边沿:单调栈中紧邻A的柱子。(如果A已经出栈,那么左边沿就是A出栈后的栈顶)而且是该柱子的右边,所以要+1.
因此,完全覆盖第index个柱子的最大矩形的面积如下(stk是单调栈)
maxArea = heights[index] * (i - (stk.top() +1))
还有一种情况。当A出栈后,单调栈为空时,那就是说明,A的左边没有比它矮的。左边沿就可以到0.
maxArea = heights[index] * (stk.empty() ? i : (i - stk.top() -1)))
可能你还有点不明白就是,那实际代码是怎么计算的?其实自习想一下就明白了,因为是取得top元素进行计算所以计算是从右边逐
渐往左边延伸。所以当整个栈排空的时候也就计算了距离右边最远的边界。
代码实现
栈实现:
int largeRectangleArea(vector<int>& h) {
stack<int> s;
h.push_back(0);
int sum = 0;
for (int i = 0; i < h.size(); ++ i) {
if (s.empty() || h[i] > h[s.top()]) s.push(i);
else {
int tmp = s.top();
s.pop();
sum = max(sum, h[tmp] * (s.empty() ? i : i - s.top() - 1));
i --;
}
}
return sum;
}
分治解法:
int largestRectangleArea(vector<int>& heights) {
if(heights.empty()) return 0;
return maxArea(heights,0,(int)heights.size()-1);
}
int maxArea(vector<int>& heights,int start, int end){
if(start > end)
return 0;
int minIndex=start;
bool sorted = true;
for(int i=start+1;i<=end;++i){
if(heights[i]<heights[i-1])
sorted=false;
if(heights[i] < heights[minIndex]){
minIndex=i;
}
}
if(sorted){//如果有序则不需要再作进一步的分治
int mx=0;
for(int i=start;i<=end;++i)
mx = max(mx,(end-i+1)*heights[i]);
return mx;
}
return max( (end-start+1)*heights[minIndex],
max( maxArea(heights,start, minIndex-1),maxArea(heights,minIndex+1, end) ) );//分治
}
算01 矩阵中包含最多1 的矩形
接下来还有道Maximal Rectangle 的题,这道题的实用价值很大:算01 矩阵中包含最多1 的矩形。
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
有了上一题的基础,这道题就可等效为上一题,对于矩阵每一行,我们将其看作直方图,立柱的高度就是行中元素往上数包含的连续1的个数。
因此每一行都可以利用上一题方法计算最大矩形,最后求出各行结果的最大值就好了。时间复杂度 O(n2)
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int H = matrix.size(), W = matrix[0].size();
int height[W+1];
int i, j , MAX = 0, leftarea = 0, rightarea = 0;
stack<int> st;
for(i = 0; i <= W; height[i] = 0, ++i);
for(i = 0; i < H; ++i){
while(!st.empty()) st.pop();
for(j = 0; j < W; ++j){
if(matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
for(int j = 0; j <= W; ++j){
while(!st.empty() && height[st.top()] > height[j]){
int tmp = st.top();
st.pop();
leftarea = (st.empty() ? tmp + 1 : tmp - st.top()) * height[tmp];
rightarea = (j - tmp - 1) * height[tmp];
if((leftarea + rightarea) > MAX) MAX = (leftarea + rightarea);
}
st.push(j);
}
}
return MAX;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!