力扣1504.统计全1子矩形

力扣1504.统计全1子矩形

• 开一个二维数组存每个点从它本身开始向左有多少连续的1

  • 遍历矩形右下角(i,j) 再遍历行k in i
  • 每一行的矩形数量 minx = min(minx,left(k,j))

•   class Solution {public:int numSubmat(vector<vector<int>>& mat) {int n = mat.size();int m = mat[0].size();vector<vector<int>> left(n,vector<int>(m));int cnt=0;for(int i=0;i<n;i++){cnt = 0;for(int j=0;j<m;j++){if(mat[i][j] == 1) cnt ++;else cnt = 0;left[i][j] = cnt;}}int res=0,minx;for(int i=0;i<n;i++){for(int j=0;j<m;j++){minx = INT_MAX;for(int k=i;k>=0;k--){minx = min(minx,left[k][j]);res += minx;}}}return res;}};