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 协议 ,转载请注明出处!