9

Maximal rectangle with 1’s in a binary matrix (Maximal Rectangle) | Runhe Tian C...

 2 years ago
source link: https://tianrunhe.wordpress.com/2012/08/03/maximal-rectangle-with-1s-in-a-binary-matrix-maximal-rectangle/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Maximal rectangle with 1’s in a binary matrix (Maximal Rectangle)

03 Aug 2012 5 Comments

by Runhe Tian in LeetCode Tags: Array, C++, Java

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

Thoughts:
If we think the matrix as a number of rows and each row is a histogram then we can reduce the problem to the Largest Rectangle in Histogram problem. So how can we view each row as histogram? Consider the following binary matrix:

11000
11000
00111
00111
00111

The largest rectangle should be 3*3, apparently. What makes up a rectangle? There are 3 columns there, if you like, and each of them contains 3 consecutive ones. So if for each row, we count how many consecutive ones we have above us, we can construct 5 histograms:

11000
22000
00111
00222
00333

Then we can compute the largest rectangle for each row and we will find out that the last row contains a maximal rectangle with area of 5 in its histogram.

Code (Java):

import java.util.Stack;
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length == 0)
return 0;
int[][] auxillary = new int[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix[i].length; ++j) {
auxillary[i][j] = Character.getNumericValue(matrix[i][j]);
}
}
for(int i = 1; i < auxillary.length; ++i) {
for(int j = 0; j < auxillary[i].length; ++j) {
if(auxillary[i][j] == 1)
auxillary[i][j] = auxillary[i-1][j] + 1;
}
}
int max = 0;
for(int i = 0; i < auxillary.length; ++i) {
max = Math.max(max, largestRectangleArea(auxillary[i]));
}
return max;
}
private int largestRectangleArea(int[] height) {
Stack<Integer> stack =
new Stack<Integer>();
int max = 0;
int i = 0;
while(i < height.length) {
if(stack.isEmpty() ||
height[i] >= stack.peek()) {
stack.push(height[i]);
i++;
}
else {
int count = 0;
while(!stack.isEmpty() &&
stack.peek() > height[i]) {
count++;
int top = stack.pop();
max = Math.max(max, top * count);
}
for(int j = 0; j < count + 1; ++j) {
stack.push(height[i]);
}
i++;
}
}
int count = 0;
while(!stack.isEmpty()) {
count++;
max = Math.max(max, stack.pop() * count);
}
return max;
}
}

Code (C++):

class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.size() == 0)
return 0;
vector<vector<int> > auxillary;
for(int i = 0; i < matrix.size(); ++i) {
vector<int> temp;
for(int j = 0; j < matrix[i].size(); ++j) {
temp.push_back(matrix[i][j] - '0');
}
auxillary.push_back(temp);
}
for(int i = 1; i < auxillary.size(); ++i) {
for(int j = 0; j < auxillary[i].size(); ++j) {
if(auxillary[i][j] == 1)
auxillary[i][j] = auxillary[i-1][j] + 1;
}
}
int maxArea = 0;
for(int i = 0; i < auxillary.size(); ++i) {
maxArea = max(maxArea, largestRectangleArea(auxillary[i]));
}
return maxArea;
}
private:
int largestRectangleArea(vector<int> &height) {
stack<int> stack_;
int maxArea = 0;
int i = 0;
while(i < height.size()) {
if(stack_.empty() ||
height[i] >= stack_.top()) {
stack_.push(height[i]);
i++;
}
else {
int count = 0;
while(!stack_.empty() &&
stack_.top() > height[i]) {
count++;
int top = stack_.top();
stack_.pop();
maxArea = max(maxArea, top * count);
}
for(int j = 0; j < count + 1; ++j) {
stack_.push(height[i]);
}
i++;
}
}
int count = 0;
while(!stack_.empty()) {
count++;
maxArea = max(maxArea, stack_.top() * count);
stack_.pop();
}
return maxArea;
}
};

Previous (Longest Palindromic Substring) Next contiguous subarray with largest sum in an array (Maximum Subarray)

5 Comments (+add yours?)

  1. af85aee181cc70bf806b3cafadd28181?s=48&d=identicon&r=GAprilBasil
    Dec 01, 2012 @ 15:45:55

    Java solution for “Maximal rectangle with 1’s in matrix”, cannot pass Leet OJ for large data. TLE

    Reply

  2. 613cb4c9f9c8b8188738b9ae094473fa?s=48&d=identicon&r=Ganurag
    Feb 07, 2013 @ 06:25:01

    plz snd me dis java program with main() on my email [email protected]

    Reply

  3. ac0925d56a2fb60074ef193cdada2578?s=48&d=identicon&r=Gnatural vitiligo treatment system ebook download
    Mar 04, 2013 @ 11:47:09

    Hi! Someone in my Facebook group shared this website with us so I came to take a look.
    I’m definitely loving the information. I’m book-marking and will be tweeting this to my followers!

    Outstanding blog and superb style and design.

    Reply

  4. 4092834470a84d5249ec531ee4f239b8?s=48&d=identicon&r=Gintelligent cruiser tips
    Jul 19, 2013 @ 15:37:44

    Fantastic post but I was wanting to know if you could write a litte more on this
    topic? I’d be very thankful if you could elaborate a little bit further. Thank you!

    Reply

  5. e7911d0926a2f1cc44e3567c50ad4ab4?s=48&d=identicon&r=Gmobile games
    Apr 15, 2014 @ 05:16:26

    Interesting blog! Is your theme custom made or did you download it from somewhere?

    A theme like yours with a few simple adjustements would really make my blog shine.
    Please let me know where you got your design. Appreciate
    it

    Reply

Leave a Reply Cancel reply


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK