algo-aha

全是1的最大子矩阵

• https://leetcode.com/problems/maximal-rectangle/

int maximalRectangle(vector<vector<char>>& matrix) {
    // 把R行C列的矩阵看作R个以第r行为底的直方图
    if (matrix.empty()) return 0;
    const int R = matrix.size(), C = matrix[0].size();
    int ans = 0;
    vector<int> h(C, 0);
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (matrix[r][c] == '0') h[c] = 0;
            else h[c]++;
        }
        ans = max(ans, largestRectangleArea(h));
    }
    return ans;
}

int largestRectangleArea(vector<int>& h) {
    // 同https://leetcode.com/problems/largest-rectangle-in-histogram/
    // 找波峰，对应找下一个更小的数
    h.push_back(0); // 右哨兵
    const int N = h.size();
    int ans = 0;
    stack<int> stk; // 栈中保存坐标
    for (int i = 0; i < N; i++) {
        while (!stk.empty() && h[i] < h[stk.top()]) {
            int peak = stk.top(); stk.pop();
            int left = stk.empty() ? -1 : stk.top();
            ans = max(ans, h[peak] * (i - left - 1));
        }
        stk.push(i);
    }
    return ans;
}

全是1的子矩阵的个数

• https://leetcode.com/problems/count-submatrices-with-all-ones/

int numSubmat(vector<vector<int>>& mat) {
    // 把R行C列的矩阵看作R个以第r行为底的直方图
    if (mat.empty()) return 0;
    const int R = mat.size(), C = mat[0].size();
    int ans = 0;
    vector<int> h(C, 0);
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (mat[r][c] == 0) h[c] = 0;
            else h[c]++;
        }
        ans += numSubmat(h);
    }
    return ans;
}

int numSubmat(vector<int>& h) { // 以第r行为底的直方图
    // 在直方图中统计全1子矩阵的个数
    // 找波峰，对应找下一个更小的数
    const int N = h.size();
    int ans = 0;
    vector<int> sum(N); // sum[i]保存右下角在(r,i)的子矩阵数
    stack<int> stk; // 保存下标
    for (int i = 0; i < N; i++) {
        while (!stk.empty() && h[i] <= h[stk.top()]) {
            stk.pop();
        }
        int lo = stk.empty() ? -1 : stk.top();
        // 现在h[lo]<h[i]
        // (lo..i]位置的高度>h[i]，贡献右下角在(r,i)的子矩阵数(i-lo)*h[i]
        // (..lo]位置的高度<=h[i]，贡献右下角在(r,i)的子矩阵数已记录在sum[lo]中
        sum[i] += (i - lo) * h[i];
        if (lo >= 0) sum[i] += sum[lo];
        ans += sum[i];

        stk.push(i);
    }
    return ans;
}

扩展：最大子矩阵和

参见：最大子段和

全是1的正方形子矩阵

• https://leetcode.com/problems/maximal-square/
• https://leetcode.com/problems/count-square-submatrices-with-all-ones/

int maximalSquare(vector<vector<char>>& matrix) {
    // 设dp[i][j]表示右下角在[i-1,j-1]的最大正方形子矩阵边长。
    // 当matrix[i-1][j-1]=='1'时，
    // dp[i][j] = 1 /*右下角的'1'*/ + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) /*即左、上、左上矩阵*/
    // 初始dp[0][..]=dp[..][0]=0
    if (matrix.empty()) return 0;
    const int M = matrix.size(), N = matrix[0].size();
    vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
    int maxlen = 0;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            if (matrix[i-1][j-1] == '1') {
                dp[i][j] = 1 + min({ dp[i-1][j-1], dp[i-1][j], dp[i][j-1] });
                maxlen = max(maxlen, dp[i][j]);
            }
        }
    }
    return maxlen * maxlen;
}

四边全为1的最大正方形

• https://leetcode.com/problems/largest-1-bordered-square/

int largest1BorderedSquare(vector<vector<int>>& grid) {
    const int R = grid.size(), C = grid[0].size();
    // 辅助矩阵统计grid[i][j]往右、往下连续1的个数
    vector<vector<int>> right(R, vector<int>(C, 0));
    vector<vector<int>> down(R, vector<int>(C, 0));
    for (int r = R - 1; r >= 0; r--) {
        for (int c = C - 1; c >= 0; c--) {
            if (grid[r][c]) {
                right[r][c] = (c + 1 < C) ? right[r][c+1] + 1 : 1;
                down[r][c] = (r + 1 < R) ? down[r+1][c] + 1 : 1;
            }
        }
    }
    
    int maxLen = 0;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            for (int len = min(right[r][c], down[r][c]); len > maxLen; len--) {
                // 检查len是否可行
                if (right[r+len-1][c] >= len && down[r][c+len-1] >= len) {
                    maxLen = len;
                    break;
                }
            }
        }
    }
    return maxLen * maxLen;
}