Description
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = [["0"]]
Output: 0
Example 3:
Input: matrix = [["1"]]
Output: 1
Constraints:
rows == matrix.lengthcols == matrix[i].length1 <= rows, cols <= 200matrix[i][j] is '0' or '1'.
Solutions
Solution 1: Monotonic Stack
We can treat each row as the base of a histogram and calculate the maximum area of the histogram for each row.
Specifically, we maintain an array heights with the same length as the number of columns in the matrix, where heights[j] represents the height of the column at the j-th position with the current row as the base. For each row, we iterate through each column:
- If the current element is '1', increment heights[j] by 1.
- If the current element is '0', set heights[j] to 0.
Then, we use the monotonic stack algorithm to calculate the maximum rectangle area of the current histogram and update the answer.
The specific steps of the monotonic stack are as follows:
- Initialize an empty stack stk to store the indices of the columns.
- Initialize two arrays left and right, representing the index of the first column to the left and right of each column that is shorter than the current column.
- Iterate through the heights array heights, first calculating the index of the first column to the left of each column that is shorter than the current column, and store it in left.
- Then iterate through the heights array heights in reverse order, calculating the index of the first column to the right of each column that is shorter than the current column, and store it in right.
- Finally, calculate the maximum rectangle area for each column and update the answer.
The time complexity is O(m × n), where m is the number of rows in matrix and n is the number of columns in matrix.
PythonJavaC++GoTypeScriptRustC#
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
heights = [0] * len(matrix[0])
ans = 0
for row in matrix:
for j, v in enumerate(row):
if v == "1":
heights[j] += 1
else:
heights[j] = 0
ans = max(ans, self.largestRectangleArea(heights))
return ans
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stk = []
left = [-1] * n
right = [n] * n
for i, h in enumerate(heights):
while stk and heights[stk[-1]] >= h:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
h = heights[i]
while stk and heights[stk[-1]] >= h:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))(code-box)
class Solution {
public int maximalRectangle(char[][] matrix) {
int n = matrix[0].length;
int[] heights = new int[n];
int ans = 0;
for (var row : matrix) {
for (int j = 0; j < n; ++j) {
if (row[j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
}
private int largestRectangleArea(int[] heights) {
int res = 0, n = heights.length;
Deque<Integer> stk = new ArrayDeque<>();
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
right[stk.pop()] = i;
}
left[i] = stk.isEmpty() ? -1 : stk.peek();
stk.push(i);
}
for (int i = 0; i < n; ++i) {
res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}
}(code-box)
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix[0].size();
vector<int> heights(n);
int ans = 0;
for (auto& row : matrix) {
for (int j = 0; j < n; ++j) {
if (row[j] == '1')
++heights[j];
else
heights[j] = 0;
}
ans = max(ans, largestRectangleArea(heights));
}
return ans;
}
int largestRectangleArea(vector<int>& heights) {
int res = 0, n = heights.size();
stack<int> stk;
vector<int> left(n, -1);
vector<int> right(n, n);
for (int i = 0; i < n; ++i) {
while (!stk.empty() && heights[stk.top()] >= heights[i]) {
right[stk.top()] = i;
stk.pop();
}
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
for (int i = 0; i < n; ++i)
res = max(res, heights[i] * (right[i] - left[i] - 1));
return res;
}
};(code-box)
func maximalRectangle(matrix [][]byte) int {
n := len(matrix[0])
heights := make([]int, n)
ans := 0
for _, row := range matrix {
for j, v := range row {
if v == '1' {
heights[j]++
} else {
heights[j] = 0
}
}
ans = max(ans, largestRectangleArea(heights))
}
return ans
}
func largestRectangleArea(heights []int) int {
res, n := 0, len(heights)
var stk []int
left, right := make([]int, n), make([]int, n)
for i := range right {
right[i] = n
}
for i, h := range heights {
for len(stk) > 0 && heights[stk[len(stk)-1]] >= h {
right[stk[len(stk)-1]] = i
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
} else {
left[i] = -1
}
stk = append(stk, i)
}
for i, h := range heights {
res = max(res, h*(right[i]-left[i]-1))
}
return res
}(code-box)
function maximalRectangle(matrix: string[][]): number {
const n = matrix[0].length;
const heights: number[] = new Array(n).fill(0);
let ans = 0;
for (const row of matrix) {
for (let j = 0; j < n; ++j) {
if (row[j] === '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
}
function largestRectangleArea(heights: number[]): number {
let res = 0;
const n = heights.length;
const stk: number[] = [];
const left: number[] = new Array(n);
const right: number[] = new Array(n).fill(n);
for (let i = 0; i < n; ++i) {
while (stk.length && heights[stk[stk.length - 1]] >= heights[i]) {
right[stk.pop()!] = i;
}
left[i] = stk.length === 0 ? -1 : stk[stk.length - 1];
stk.push(i);
}
for (let i = 0; i < n; ++i) {
res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}(code-box)
impl Solution {
pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
let n = matrix[0].len();
let mut heights = vec![0; n];
let mut ans = 0;
for row in matrix {
for j in 0..n {
if row[j] == '1' {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
ans = ans.max(Self::largest_rectangle_area(&heights));
}
ans
}
fn largest_rectangle_area(heights: &Vec<i32>) -> i32 {
let mut res = 0;
let n = heights.len();
let mut stk: Vec<usize> = Vec::new();
let mut left = vec![0; n];
let mut right = vec![n; n];
for i in 0..n {
while let Some(&top) = stk.last() {
if heights[top] >= heights[i] {
right[top] = i;
stk.pop();
} else {
break;
}
}
left[i] = if stk.is_empty() { -1 } else { stk[stk.len() - 1] as i32 };
stk.push(i);
}
for i in 0..n {
res = res.max(heights[i] * (right[i] as i32 - left[i] - 1));
}
res
}
}(code-box)
public class Solution {
public int MaximalRectangle(char[][] matrix) {
int n = matrix[0].Length;
int[] heights = new int[n];
int ans = 0;
foreach (var row in matrix) {
for (int j = 0; j < n; ++j) {
if (row[j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
ans = Math.Max(ans, LargestRectangleArea(heights));
}
return ans;
}
private int LargestRectangleArea(int[] heights) {
int res = 0, n = heights.Length;
Stack<int> stk = new Stack<int>();
int[] left = new int[n];
int[] right = new int[n];
Array.Fill(right, n);
for (int i = 0; i < n; ++i) {
while (stk.Count > 0 && heights[stk.Peek()] >= heights[i]) {
right[stk.Pop()] = i;
}
left[i] = stk.Count == 0 ? -1 : stk.Peek();
stk.Push(i);
}
for (int i = 0; i < n; ++i) {
res = Math.Max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}
}(code-box)
