Maximal Rectangle Algorithm
The Maximal Rectangle Algorithm is an advanced computational technique used to find the largest rectangular area within a binary matrix (i.e., a grid containing only 0s and 1s). This problem is common in computer science, image processing, and data analysis, where one needs to identify the largest sub-rectangle that is entirely filled with 1s or some specific value. The algorithm has numerous applications, including image segmentation, object recognition, and pattern matching, among others.
The algorithm typically employs dynamic programming, which allows it to efficiently solve the problem by breaking it down into smaller overlapping sub-problems. The concept of the Maximal Rectangle Algorithm is based on the largest rectangle in a histogram problem, which can be solved using a stack-based approach. By iterating through the rows of the binary matrix, one can treat each row as a histogram and use the histogram algorithm to find the largest rectangle that ends at that row. The algorithm can be further optimized by keeping track of the heights of the rectangles for each column and using this information to update the heights for subsequent rows as the algorithm progresses. This approach ensures that the Maximal Rectangle Algorithm has a time complexity of O(mn), where m and n are the dimensions of the binary matrix.
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int row = matrix.size();
if (row == 0) return 0;
int col = matrix[0].size();
int result = 0;
int height[col];
memset(height, 0, sizeof(int)*col);
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == '1')
height[j] += 1;
else
height[j] = 0;
}
int rect = getLargestRectInHistogram(height, col);
result = max(result, rect);
}
return result;
}
int getLargestRectInHistogram(const int height[], int n) {
int width[n];
stack<int> minHeight;
int result = 0;
for (int i = 0; i < n; i++) {
while (!minHeight.empty() && height[i] <= height[minHeight.top()])
minHeight.pop();
int left = minHeight.empty() ? -1 : minHeight.top();
width[i] = i - left - 1;
minHeight.push(i);
}
while (!minHeight.empty())
minHeight.pop();
for (int i = n-1; i >= 0; i--) {
while (!minHeight.empty() && height[i] <= height[minHeight.top()])
minHeight.pop();
int right = minHeight.empty() ? n : minHeight.top();
width[i] += right - i - 1;
minHeight.push(i);
}
for (int i = 0; i < n; i++) {
result = max(result, height[i] * (width[i] + 1));
}
return result;
}
};
