算法设计与分析-Week13

发表于 | 更新于

Maximal Square

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

解题思路

本题要在一个01矩阵中找到一个最大方阵的面积，这个方阵包含的都是1.
思路一： 考虑到一个方阵的面积取决于它的右下角能够到达哪里，于是我用一个相同大小的矩阵v，v[i][j]表示以i，j为右下角的方阵的最大边长，于是得到状态方程：当矩阵的第i行第j列元素为1时，v[i][j] = min(v[i-1][j], v[i][j-1], v[i-1][j-1]) + 1；当矩阵的第i行第j列元素为0时，v[i][j] = 0。并在一开始将矩阵v的第一行和第一列初始化，矩阵v的值与01矩阵对应值相等，整个算法的空间复杂度与时间复杂度均为\(O(nm)\)。
思路二： 考虑到实际上每次计算v[i][j]的值时，只需要用到v[i-1][j], v[i][j-1], v[i-1][j-1]，所以实际上可以只用一个大小为n+1的数组存储，将空间复杂度降为\(O(n)\)。

源代码

思路一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int max = 0;
        int n = matrix.size();
        if(n == 0) return 0;
        int m = matrix[0].size();
        vector<vector<int>> v(n, vector<int>(m, 0));
        for(int i = 0; i < m; i++) {
            if(matrix[0][i] == '1') {
                v[0][i] = 1;
                max = 1;
            }
        }
        for(int i = 0; i < n; i++) {
            if(matrix[i][0] == '1') {
                v[i][0] = 1;
                max = 1;
            }
        }
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(matrix[i][j] == '1') {
                    int temp = min(v[i][j-1], v[i-1][j]);
                    v[i][j] = min(temp, v[i-1][j-1]) + 1;
                    if(v[i][j] > max) max = v[i][j];
                }
            }
        }
        return max * max;
    }
};

思路二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int max = 0;
        int n = matrix.size();
        if(n == 0) return 0;
        int m = matrix[0].size();
        vector<int> v(n + 1, 0);
        int pre = 0;
        for(int j = 0; j < m; j++) {
            for(int i = 1; i < n + 1; i++) {
                int temp = v[i];
                if(matrix[i - 1][j] == '1') {
                    v[i] = min(v[i-1], min(v[i], pre)) + 1;
                    if(v[i] > max) max = v[i];
                } else {
                    v[i] = 0;
                }
                pre = temp;
            }
        }
        return max * max;
    }
};
0%