LeetCode HOT100 - 最大正方形

因为数据量只有 300 ，因此想到使用暴力查询是否有正方形满足

这样的话就是写一个二维前缀和

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> a(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = matrix[i][j] - '0';
            }
        }
        vector<vector<int>> pre(n + 1, vector<int>(m + 1, 0));
        pre[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] + a[i][j] - pre[i][j];
            }
        }
        int ans = 0;
        for (int i = 0; i < min(n, m); i++) {
            for (int j = 0; j + i < n; j++) {
                for (int k = 0; k + i < m; k++) {
                    if (pre[j + i + 1][k + i + 1] - pre[j][k + i + 1] - pre[j + i + 1][k] + pre[j][k] == (i + 1) * (i + 1)) {
                        ans = (i + 1) * (i + 1);
                        break;
                    }
                }
                if (ans == (i + 1) * (i + 1)) {
                    break;
                }
            }
        }
        return ans;
    }
};

如果要优化一下的话可以考虑正方形边长那里使用二分，因为这里显然是有二段性的

当然，更优的方法是使用 dp，因为前一个状态的最优转移到当前形式肯定也是最优的
dp 的话，接着考虑子问题的形式来设计状态

不难想到，令 dp[i][j] 表示 i, j 为右下角的矩形中最大的边长，当然，要限制 (i, j) 为 1，不然不好转移

转移的时候仍然要从二维的角度来做

想想什么情况下可以加

1 1 1
1 1 1
1 1 x
这种情况下才能加 1
结合我们状态的设计的话，可以看作 (0, 0)~(1, 1), (0, 1)~(1, 2), (1, 0)~(2, 1) 三个都要是全 1 正方形

这个刚好可以用 min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 来刻画

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    dp[i + 1][j + 1] = min({dp[i][j], dp[i][j + 1], dp[i + 1][j]}) + 1;
                    ans = max(ans, dp[i + 1][j + 1]);
                } 
            }
        }
        return ans * ans;
    }
};

还有一个很巧妙的位运算的解法 https://leetcode.cn/problems/maximal-square/solutions/237808/fen-xiang-yi-ge-bu-yong-dong-tai-gui-hua-cai-yong-

c++ 的话可以用 bitset 来实现

当然从时间复杂度的角度来说并不比 dp 更优

class Solution {
public:
    static const int MAXM = 300;

    int cal(const bitset<MAXM>& bs, int m) {
        int cur = 0, res = 0;
        for (int j = 0; j < m; ++j) {
            if (bs[j]) {
                cur++;
                res = max(res, cur);
            } else {
                cur = 0;
            }
        }
        return res;
    }

    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<bitset<MAXM>> rows(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (matrix[i][j] == '1') {
                    rows[i].set(j);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            bitset<MAXM> cur = rows[i];
            for (int j = i; j < n; ++j) {
                cur &= rows[j];
                int h = j - i + 1;
                int w = cal(cur, m);
                res = max(res, min(h, w));
                if (w < h) {
                    break;
                }
            }
        }
        return res * res;
    }
};