最大正方形

  1. use std::cmp::max;
  2. use std::cmp::min;
  4. /// Maximal Square
  5. /// Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
  6. /// https://leetcode.com/problems/maximal-square/
  7. ///
  8. /// Arguments:
  9. ///     * `matrix` - an array of integer array
  10. /// Complexity
  11. ///     - time complexity: O(n^2),
  12. ///     - space complexity: O(n),
  13. pub fn maximal_square(matrix: &mut Vec<Vec<i32>>) -> i32 {
  14.     if matrix.is_empty() {
  15.         return 0;
  16.     }
  18.     let rows = matrix.len();
  19.     let cols = matrix[0].len();
  20.     let mut result: i32 = 0;
  22.     for row in 0..rows {
  23.         for col in 0..cols {
  24.             if matrix[row][col] == 1 {
  25.                 if row == 0 || col == 0 {
  26.                     result = max(result, 1);
  27.                 } else {
  28.                     let temp = min(matrix[row - 1][col - 1], matrix[row - 1][col]);
  30.                     let count: i32 = min(temp, matrix[row][col - 1]) + 1;
  31.                     result = max(result, count);
  33.                     matrix[row][col] = count;
  34.                 }
  35.             }
  36.         }
  37.     }
  39.     result * result
  40. }
  42. #[cfg(test)]
  43. mod tests {
  44.     use super::*;
  46.     #[test]
  47.     fn test() {
  48.         assert_eq!(maximal_square(&mut vec![]), 0);
  50.         let mut matrix = vec![vec![0, 1], vec![1, 0]];
  51.         assert_eq!(maximal_square(&mut matrix), 1);
  53.         let mut matrix = vec![
  54.             vec![1, 0, 1, 0, 0],
  55.             vec![1, 0, 1, 1, 1],
  56.             vec![1, 1, 1, 1, 1],
  57.             vec![1, 0, 0, 1, 0],
  58.         ];
  59.         assert_eq!(maximal_square(&mut matrix), 4);
  61.         let mut matrix = vec![vec![0]];
  62.         assert_eq!(maximal_square(&mut matrix), 0);
  63.     }
  64. }