`
huntfor
  • 浏览: 201663 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Maximal Rectangle

 
阅读更多

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^2 * m ^2)不用试估计也会超时了,看了讨论组里面有位大神提供了这样的思路:

This question is similar as [Largest Rectangle in Histogram]:

You can maintain a row length of Integer array H recorded its height of '1's, and scan and update row by row to find out the largest rectangle of each row.

 什么意思呢?给大家用图例展示一下:想看详细步骤的可以戳这里

 

虽然上图画错了,但是还是表达出了大神的意思:

对原矩阵matrix的每一行生成并维护一个int[]数组。

这个数组表示以该行为底线,与上面所有行组成的高度数组,比如第三行是0 1 1 1,但是matrix[1][3] 也是1,因此最有一个元素的高度应该是2(图中只花了1个高度)

思考一下:第2行第三个元素是0,但是它上面是1,为什么高度和是0而不是1呢?(想不通面壁去)

因此我们可以由matrix的每一行生成一个int[]高度数组,是不是回到了[Largest Rectangle in Histogram]?

 

因此我们要做的就是对每一行生成一个int[]数组。再对每个int[]数组调用Largest Rectangle in Histogram中的方法即可。

 

   public int maximalRectangle(char[][] matrix) {
    	if(matrix == null || matrix.length == 0) return 0;
    	int rowCount = matrix.length;
    	int columnCount = matrix[0].length;
    	int[][] rectangle = new int[rowCount][columnCount];
    	for(int i = 0; i < rowCount; i++){
    		for(int j = 0; j < columnCount;j++){
    			if(i == 0){
    				rectangle[i][j] = matrix[i][j] == '1' ? 1 : 0;
    			}else{
    				rectangle[i][j] = matrix[i][j] == '1' ? 1 + rectangle[i - 1][j] : 0;
    			}
    		}
    	}
    	
    	int maxArea = 0;
    	for(int i = 0; i < rowCount; i++){
    		int tem = getLargestRectangle(rectangle[i]);
    		maxArea = tem > maxArea ? tem : maxArea;
    	}
    	return maxArea;
    }

 下面是Largest Rectangle in Histogram中的源代码,一模一样,而且两道题在leetcode中的位置也是挨着的,算是提示吗?

 private int getLargestRectangle(int[] height){
   
    	int[] copy = new int[height.length + 1];
		copy = Arrays.copyOf(height, height.length + 1);
		Stack<Integer> stack = new Stack<Integer>();
		int maxArea = 0;
		int i = 0;
		while(i < copy.length){
			if(stack.isEmpty() || copy[stack.peek()] < copy[i]){
				stack.push(i++);
			}else{
				int num = stack.pop();
				maxArea = Math.max(maxArea,copy[num] * (stack.isEmpty() ? i : i - stack.peek() - 1));
			}
		}
    	return maxArea;
    }

 

 

分享到:
评论

相关推荐

    java-leetcode题解之Maximal Rectangle.java

    java java_leetcode题解之Maximal Rectangle.java

    python-leetcode题解之085-Maximal-Rectangle

    python python_leetcode题解之085_Maximal_Rectangle

    js-leetcode题解之85-maximal-rectangle.js

    javascript js_leetcode题解之85-maximal-rectangle.js

    c语言-leetcode题解之0085-maximal-rectangle.zip

    c语言基础 c语言_leetcode题解之0085_maximal_rectangle.zip

    LeetCode C++全解

    1. Introduction 2. Array i. Remove Element ... Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    Leetcode题目+解析+思路+答案.pdf

    - **Maximal Rectangle**:在二维矩阵中找到最大的矩形。 - **Palindrome Number**:判断一个数字是否是回文数。 - **Search a 2D Matrix**:在二维矩阵中搜索目标值。 - **Search for a Range**:在一个排序...

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码...Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar

    lrucacheleetcode-leetcode:leetcode

    Rectangle Monotonic stack for 2d array 239. Sliding Window Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. Recover Binary Search Tree 109. ...

    dna匹配leetcode-leetcode:leetcode刷题

    Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int&gt; Fraction to Recurring Decimal ...

    leetcode316-LeetCode:leetcode的解决方案

    leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...

    leetcode中国-leetcode:leetcode刷题

    maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 ...

    LeetCode leetcode部分题解答代码实现

    * Maximal Rectangle:给定一个矩形,返回矩形中的最大子矩形。这个题目需要使用动态规划的思想,将矩形分解成更小的矩形,并找到最大矩形。 2. 位操作 位操作是 LeetCode 中的一种常见题型,下面是一些关于位操作...

    leetcode和oj-ProgProblems:程序问题

    leetcode 和 oj 编程问题 在线裁判网站问题解决方案 如果您遇到这个问题并对如何更好地完成某些解决方案有建议或意见,欢迎您。 palin.ml : ...MaximalRectangle : oj.leetcode 问题的java解决方案

    LeetCode练习答案

    - **最大矩形(Maximal Rectangle)**: 在由'0'和'1'组成的二维矩阵中,找到只包含'1'的最大矩形,并返回其面积。 - **回文数(Palindrome Number)**: 判断一个整数是否是回文数。 - **搜索二维矩阵(Search a 2D Matrix...

    3、动态规划必练题(含解法).pdf

    12. **Maximal Rectangle** (最大的矩形) 在一个01矩阵中找到最大的1构成的矩形。利用汉诺塔和单调栈解决。 13. **Maximal Square** (最大的正方形) 找到01矩阵中最大的全1子矩阵。可以使用动态规划和单调栈或...

Global site tag (gtag.js) - Google Analytics