本文主要是介绍【数据结构-二维前缀和】力扣1504. 统计全 1 子矩形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。
示例 1：
输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。
示例 2：
输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
提示：
1 <= m, n <= 150
mat[i][j] 仅包含 0 或 1
法一：枚举
class Solution {
public:int numSubmat(vector<vector<int>>& mat) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m, vector<int>(n));for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(j == 0){dp[i][j] = mat[i][j];}else if(mat[i][j] != 0){dp[i][j] = dp[i][j-1] + 1;}else{dp[i][j] = 0;} }}int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int col = dp[i][j];for(int k = i; k >=0 && col; k--){col = min(dp[k][j], col);ans += col;}}}return ans;}
};
时间复杂度：O(nm^2)
空间复杂度：O(mn)
这道题要求的是子矩形，那么一个矩形如何确定，实际上只要知道两个顶点就可以确定一个矩形。所以我们可以想到遍历矩阵每个元素作为矩形的右下角，然后来找左上顶点。既然右下角顶点已经确定，假设当矩形的高也知道，那么顶边的长度就是符合右下角为顶点，高确定的矩形个数。
所以我们要做的就是遍历矩阵每个元素为矩形右下角，然后在不断假设高，然后找到在不同高的情况下矩形的顶边最长是多少。
所以为了找到顶边，所以开始使用的dp就是为了计算在某一格元素向左的最大边长是多少。
我们将每个元素为右下角能构成的矩形数量都计入ans中，最后返回的ans就是所有符合要求全为1的子矩阵数量。
这道题还有单调栈优化，后面有时间补充
这篇关于【数据结构-二维前缀和】力扣1504. 统计全 1 子矩形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
