40 lines
1.2 KiB
Rust
40 lines
1.2 KiB
Rust
use std::cmp;
|
|
|
|
impl Solution {
|
|
fn indices(rows: usize, cols: usize) -> impl Iterator<Item = (usize, usize)> {
|
|
(0..rows * cols).map(move |i| (i / cols, i % cols))
|
|
}
|
|
|
|
fn get(dp: &[Vec<(usize, usize)>], y: usize, x: usize) -> (usize, usize) {
|
|
if y > dp.len() || x > dp[y].len() {
|
|
return (0, 0);
|
|
}
|
|
|
|
dp[y][x]
|
|
}
|
|
|
|
pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
|
|
let mut found_max = 0;
|
|
let mut dp = vec![vec![(0, 0); matrix[0].len()]; matrix.len()];
|
|
|
|
for (y, x) in Self::indices(matrix.len(), matrix[0].len()) {
|
|
if matrix[y][x] != '1' {
|
|
continue;
|
|
}
|
|
|
|
let width = 1 + Self::get(&dp, y, x - 1).0;
|
|
let height = 1 + Self::get(&dp, y - 1, x).1;
|
|
dp[y][x] = (width, height);
|
|
|
|
found_max = cmp::max(found_max, cmp::max(width, height));
|
|
|
|
let mut min_width = width;
|
|
for yy in ((y - height + 1)..y).rev() {
|
|
min_width = cmp::min(min_width, dp[yy][x].0);
|
|
found_max = cmp::max(found_max, min_width * (y - yy + 1));
|
|
}
|
|
}
|
|
|
|
found_max.try_into().unwrap()
|
|
}
|
|
}
|