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.

方法

使用两个矩阵,分别记录每一行连续的1的个数以及每一列连续的1的个数。

    public int maximalRectangle(char[][] matrix) {
        int lenX = matrix.length;
        if (lenX == 0) {
            return 0;
        }
        int lenY = matrix[0].length;
        int[][] maxRec = new int[lenX][lenY];
        int[][] height = new int[lenX][lenY];
        int[][] length = new int[lenX][lenY];
        for (int i = 0; i < lenX; i++) {
        	for (int j = 0; j < lenY; j++) {
        		if (matrix[i][j] == '1') {
        			if (j == 0) {
        				length[i][j] = 1;
        			} else {
        				length[i][j] = length[i][j - 1] + 1;
        			}

        			if (i == 0) {
        				height[i][j] = 1;
        			} else {
        				height[i][j] = height[i - 1][j] + 1;
        			}
        		} else {
        			length[i][j] = 0;
        			height[i][j] = 0;
        		}
        	}
        }

        for (int i = 0; i < lenX; i++) {
            for (int j = 0; j < lenY; j++) {
            	int h = height[i][j];
            	int l = length[i][j];
            	int minHeight = h;
            	int max = 0;
            	for (int k = 1; k <= l; k++) {
            		minHeight = Math.min(minHeight, height[i][j + 1 - k]);
            		max = Math.max(max, k * minHeight);
            	}
            	maxRec[i][j] = max;
            }
        }
        int max = 0;
        for (int i = 0; i < lenX; i++) {
            for (int j = 0; j < lenY; j++) {
                if (maxRec[i][j] > max) {
                    max = maxRec[i][j];
                }
            }
        }
        return max;
    }

Maximal Rectangle,布布扣,bubuko.com

时间: 06-09

Maximal Rectangle的相关文章

LeetCode: Maximal Rectangle

LeetCode: 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. 地址:https://oj.leetcode.com/problems/maximal-rectangle/ 算法:要解决这道题,得利用Largest Rectangle in Histogram这道题的解法

LeetCode: Maximal Rectangle [085]

[题目] Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. [题意] 给定一个由0和1填充的二维矩阵,找一个全是1的最大矩形 [思路] 扫描二维矩阵,凡是扫到值为1的块时候,以当前块为矩形的左上角区块拓展,找最大矩阵. 先找出以每个"1"区块为左上角区块的最大矩形,然后求出最大全局的最大矩形. 以下图为

Leetcode:Maximal Rectangle 最大全1子矩阵

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(n)时间内求出 最大的矩形面积 如果我们把每一行看成x坐标,那高度就是从那一行开始往上数的1的个数. 利用 最大矩形面积 的方法,在O(n2)时间内就可以求出每一行形成的“柱状

84. Largest Rectangle in Histogram *HARD* 柱状图求最大面积 85. Maximal Rectangle *HARD*

1. 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 large

LeetCode 85. Maximal Rectangle

1 class Solution { 2 public: 3 int maximalRectangle(vector<vector<char>>& matrix) { 4 /** largest rectangle based solution **/ 5 if(matrix.size()<=0 || matrix[0].size()<=0) 6 return 0; 7 int m=matrix.size(); 8 int n=matrix[0].size()+

LeetCode OJ: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. 求出0,1矩阵中的最大矩形区域: DP问题,可以使用数组记下当前行位置之前的所有1的个数,然后用一个三重循环来找以(i,j)为右下角的矩形的最大的面积,比较得到最大值.这样做复杂度还是比较高的.但是胜在简单,代码如下所示: 1 class Solution { 2

[leedcode 85] 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. public class Solution { public int maximalRectangle(char[][] matrix) { //利用上题的思路,先求出每一列的连续1个数,保存在DP二维数组中,然后对每一行进行findRectangle if(ma

(每日算法)Leetcode --- Maximal Rectangle(最大子矩阵)

求在0-1矩阵中找出面积最大的全1矩阵 Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 首先,想使用遍历两次的暴力方法解决是不靠谱的,先打消这个念头. 这道题的解法灵感来自于 Largest Rectangle in Histogram 这道题,假设我们把矩阵沿着某一行切下来,然后把切的行作为底面,将自底面往上

【leetcode】Maximal Rectangle (hard)★

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 找到01矩形中最大的全1子矩阵. 我自己的思路: 我先用一个跟输入相同大小的矩阵numInCol 存储从当前位置开始向下有多少连续的1. 如 1 0 1 0 1 1 1 1 1 其numInCol 是 1 0 3 0 2 2 1 1 1 然后用一个变量tmpans