[Leetcode] Largest Rectangle (in Histogram) 最大矩形

邹强发布于2019-08-14 12:24 / 1192人阅读

摘要：以此类推，如果一直到栈为空时，说明刚出来的竖条之前的所有竖条都比它自己高，不然不可能栈为空，那我们以左边全部的宽度作为长方形的宽度。

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram"s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

暴力法 复杂度

时间 O(N^2) 空间 O(1)

思路

最直观的方法是对每个竖条，都向前向后计算下最大的面积，这样虽然时间复杂度很高，但是不用额外空间。

栈法 复杂度

时间 O(N) 空间 O(N)

思路

遍历数组（直方图），如果后一个竖条高于或等于前一个竖条，则将其下标push进栈，如果后一个竖条（假设它的下标为i）较矮，说明可以开始计算前一个竖条(i-1)及之前那块上升区域最大的长方形面积了，这时将栈顶的竖条的下标pop出来，计算该竖条的面积。然后再看pop过后栈顶竖条(i-2)和后一个竖条(i)的大小关系，如果栈顶竖条(i-2)较矮，说明又构成了一个连续上升区域，则将后一个竖条(i)push进栈，否则继续计算栈顶竖条(i-2)的面积，这里要注意，因为(i-2)竖条比(i-1)竖条要靠左，所以i-2竖条能构成的最大长方形的宽度可以达到2，宽度的计算方法是用后一个竖条的下标i，减去再pop一个元素后栈顶竖条的下标(i-3)，再加上1。以此类推，如果一直pop到栈为空时，说明刚pop出来的竖条之前的所有竖条都比它自己高，不然不可能栈为空，那我们以左边全部的宽度作为长方形的宽度。这里计算宽度时，要减去上一个竖条的位置，而不是减去当前竖条的位置，因为有可能上一个竖条和当前竖条之间已经有些竖条被pop掉了，但他们肯定是高于当前竖条的，所以可以计算到宽度中。

代码

public class Solution {
    public int largestRectangleArea(int[] height) {
        if(height.length == 0) return 0;
        Stack stk = new Stack();
        int i = 1, max = height[0];
        stk.push(0);
        while(i < height.length || (i == height.length && !stk.isEmpty())){
            // i==height.length 说明目前栈顶已经是最后一个竖条，那就要开始pop了
            if(i != height.length && ( stk.isEmpty() || height[i] >= height[stk.peek()] )){
                stk.push(i);
                i++;
            } else {
                // pop后栈为空的话说明之前所有竖条都比刚pop出来的矮
                int top = height[stk.pop()];
                int currMax = !stk.isEmpty() ? top * (i - stk.peek() - 1) : top * i;
                max = Math.max(currMax, max);
            }
        }
        return max;
    }
}

Maximal Rectangle

Given a 2D binary matrix filled with 0"s and 1"s, find the largest rectangle containing all ones and return its area.

动态规划 + 栈 复杂度

时间 O(NM) 空间 O(M)

思路

这题的解法基于上题。要求最大的矩形，实际上可以将矩阵的每一行，转化为上一题的直方图，而直方图的每个竖条的数字，就是该行对应坐标正上方，向上方向有多少个连续的1。要转化为直方图，方法是每一行的数值都累加上一行计算出来的数值，而第一行的数值就是本身。如果原始矩阵中遇到0，则累加中断，重新置0。

0 0 1 1 0 -> 0 0 1 1 0
0 0 1 1 0 -> 0 0 2 2 0
1 1 0 0 0 -> 1 1 0 0 0
1 1 1 0 0 -> 2 2 1 0 0

代码

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        if(matrix.length == 0) return 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                // 如果是第一行就是自身，如果遇到0则停止累加
                dp[i][j] =  i == 0 ? matrix[i][j] - "0" : matrix[i][j] == "1" ? dp[i-1][j] + matrix[i][j] - "0" : 0;
            }
        }
        for(int i = 0; i < dp.length; i++){
            //找每行的最大矩形
            int tmp = findRowMax(i, dp);
            max = Math.max(max, tmp);
        }
        return max;
    }
    
    private int findRowMax(int row, int[][] matrix){
        if(matrix[row].length== 0) return 0;
        Stack stk = new Stack();
        int i = 1, max = matrix[row][0];
        stk.push(0);
        while(i < matrix[row].length || (i == matrix[row].length && !stk.isEmpty())){
            if(i != matrix[row].length && ( stk.isEmpty() || matrix[row][i] >= matrix[row][stk.peek()] )){
                stk.push(i);
                i++;
            } else {
                int top = matrix[row][stk.pop()];
                int currMax = !stk.isEmpty() ? top * (i - stk.peek() - 1) : top * i;
                max = Math.max(currMax, max);
            }
        }
        return max;
    }
}

GPU云服务器云服务器 HISTOGRAM Largest Rectangle LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64450.html

leetcode84. Largest Rectangle in Histogram

摘要：题目要求即找到图中可以组合而成的面积最大的矩形。从而我们可以知道该矩形在水平方向上的最大扩展程度。也就是说，栈中数据记录了最远左侧下标，而当前的矩形则是最远右侧下标。当我们不采用数据结构时，寻找和计算的过程需要的时间复杂度。题目要求 Given n non-negative integers representing the histograms bar height where t...

Harpsichord1207 2019-08-15 10:55 评论0 收藏0
Largest Rectangle in Histogram

摘要：而最大的矩形一定满足两个边界的高度小于该矩形的高度这个条件如果不满足的话，边界也可以被添加进来计算而不破坏矩形的形状，此时不为最大，因此找出所有这样的矩形就一定可以在其中找出面积最大的矩形。 Problem Given n non-negative integers representing the histograms bar height where the width of e...

vvpvvp 2019-07-24 17:33 评论0 收藏0
[LintCode] Largest Rectangle in Histogram

摘要：只要出现当前右边界高度小于等于栈顶元素高度的情况，就取出栈顶元素当前遍历过最高的并对这个元素进行取最大矩形的运算。 Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest ...

alighters 2019-08-14 15:27 评论0 收藏0
[LeetCode] 84. Largest Rectangle in Histogram

Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. showImg(https://segmentfault.com/img...

BaronZhang 2019-08-16 14:25 评论0 收藏0
84. Largest Rectangle in Histogram

摘要：要求一个矩形的面积，要知道高和宽。如果每次确定高度为然后调用一个找到左右边界，即不小于的最左和最右。这是一个明显的算法，每次扫描都会重走整个。一个递增序列这种，我们知道可以够成的矩形是会不断增大的。递增序列预处理，递减的时候计算。 showImg(https://segmentfault.com/img/bVoQel); For example, Given heights = [2,...

melody_lql 2019-08-14 18:01 评论0 收藏0