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.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j] is '0' or '1'.
Solutions
Solution 1: Monotonic Stack
We treat each row as the base of the histogram, and calculate the maximum area of the histogram for each row.
The time complexity is $O(m \times n)$, where $m$ represents the number of rows in $matrix$, and $n$ represents the number of columns in $matrix$.
implSolution{#[allow(dead_code)]pubfnmaximal_rectangle(matrix:Vec<Vec<char>>)->i32{letn=matrix[0].len();letmutheights=vec![0;n];letmutret=-1;forrowin&matrix{Self::array_builder(row,&mutheights);ret=std::cmp::max(ret,Self::largest_rectangle_area(heights.clone()));}ret}/// Helper function, build the heights array according to the input#[allow(dead_code)]fnarray_builder(input:&Vec<char>,heights:&mutVec<i32>){for(i,&c)ininput.iter().enumerate(){heights[i]+=matchc{'1'=>1,'0'=>{heights[i]=0;0}_=>panic!("This is impossible"),};}}/// Helper function, see: https://leetcode.com/problems/largest-rectangle-in-histogram/ for details#[allow(dead_code)]fnlargest_rectangle_area(heights:Vec<i32>)->i32{letn=heights.len();letmutleft=vec![-1;n];letmutright=vec![-1;n];letmutstack:Vec<(usize,i32)>=Vec::new();letmutret=-1;// Build left vectorfor(i,h)inheights.iter().enumerate(){while!stack.is_empty()&&stack.last().unwrap().1>=*h{stack.pop();}ifstack.is_empty(){left[i]=-1;}else{left[i]=stack.last().unwrap().0asi32;}stack.push((i,*h));}stack.clear();// Build right vectorfor(i,h)inheights.iter().enumerate().rev(){while!stack.is_empty()&&stack.last().unwrap().1>=*h{stack.pop();}ifstack.is_empty(){right[i]=nasi32;}else{right[i]=stack.last().unwrap().0asi32;}stack.push((i,*h));}// Calculate the max areafor(i,h)inheights.iter().enumerate(){ret=std::cmp::max(ret,(right[i]-left[i]-1)**h);}ret}}