Problem:1504. 统计全 1 子矩形

思路：为了不重不漏的统计完答案，我们可以枚举每个子矩阵的右下角位置，然后在统计相加。

Accode:

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        vector<vector<int>> sum(mat.size());
        for (int i = 0; i < mat.size(); i++) {
            int tem_sum = 0;
            for (int j = 0; j < mat[i].size(); j++) {
                if (mat[i][j]) {
                    tem_sum++;
                } else {
                    tem_sum = 0;
                }
                sum[i].push_back(tem_sum);
            }
        }
        int ans = 0;
        for (int i = 0; i < sum.size(); i++) {
            for (int j = 0; j < sum[i].size(); j++) {
                if (!sum[i][j])
                    continue;
                ans += sum[i][j];
                int min_s = sum[i][j];
                for (int k = i - 1; k >= 0; k--) {
                    if (!sum[k][j]) {
                        break;
                    }
                    min_s = min(min_s,sum[k][j]);
                    ans += min_s;
                }
            }
        }
        return ans;
    }
};

时间复杂度：$o(n^3)$

进一步优化：在上述基础上,单调栈做法

母题：母题

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> pre(m);
        //算出当前行以mat[i][j]结尾连续的1的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j]==0){
                    pre[i].push_back(0);
                }
                else if(j>0 && mat[i][j]){
                    pre[i].push_back(pre[i].back()+1);
                }
                else{
                    pre[i].push_back(1);
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < n; j++) {
            int sum = 0;
            stack<int> sta;
            for (int i = 0; i < m; i++) {
                while (sta.size() && pre[sta.top()][j] >= pre[i][j]) {
                    int start = sta.top();
                    sta.pop();
                    if (sta.size()) {
                        sum -= (start - sta.top()) * pre[start][j];
                    } else {
                        sum -= (start + 1) * pre[start][j];
                    }
                }
                if (sta.size()) {
                    sum += pre[i][j] * (i - sta.top());
                } else {
                    sum += pre[i][j] * (i + 1);
                }
                sta.push(i);
                ans += sum;

            }
        }
        return ans;
    }
};

时间复杂度：$o(n^2)$