最大正方形

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. }