maximal-rectangle.rs

#![allow(dead_code, unused, unused_variables, non_snake_case)]

fnmain(){}

structSolution;

implSolution{
pubfnmaximal_rectangle(matrix:Vec<Vec<char>>) -> i32{
// 构造柱状图
letmut v = vec![vec![]; matrix.len()];

for i in0..matrix.len(){
 v[i].push(0);
for j in0..matrix[0].len(){
if matrix[i][j] == '0'{
 v[i].push(0);
}else{
let value = if i == 0{1}else{ v[i - 1][j + 1] + 1};
 v[i].push(value);
}
}

 v[i].push(0);
}

letmut ans = 0;

for v1 in v {
let len = v1.len();
letmut stack = vec![];

for v2 in0..len {
while !stack.is_empty() && v1[stack[stack.len() - 1]] >= v1[v2]{
let top = stack.pop().unwrap();
 ans = ans.max(v1[top]*(v2 - *stack.last().unwrap_or(&0) - 1)asi32);
}

 stack.push(v2);
}

let last = *stack.last().unwrap_or(&0);

while !stack.is_empty(){
let top = stack.pop().unwrap();
 ans = ans.max(v1[top]*(last - *stack.last().unwrap_or(&0))asi32);
}
}

 ans
}
}