标签搜索

目 录CONTENT

文章目录

力扣--统计全1子矩阵.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 1,832 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

力扣--统计全1子矩阵

@[toc]

一、题目描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二、分析

方法一:枚举

  •  首先很直观的想法,我们可以枚举矩阵中的每个位置 (i,j),统计以其作为右下角时,有多少个元素全部都是 1的子矩形,那么我们就能不重不漏地统计出满足条件的子矩形个数。
  •  那么枚举以后,我们怎么统计满足条件的子矩形个数呢?
  •  既然是枚举以 (i,j) 作为右下角的子矩形个数,那么我们可以直接暴力地枚举左上角 (k,y),看其组成的矩形是否满足条件,时间复杂度为 O(nm)。但这样无疑会使得时间复杂度变得很高,我们需要另寻他路。
  •  我们预处理row 数组,其中row[i][j] 代表矩阵中 (i,j) 向左延伸连续 1 的个数,容易得出递推式:

在这里插入图片描述

  •  有了row 数组以后,如果要统计以 (i,j) 为右下角满足条件的子矩形,我们就可以枚举子矩形的高,即第 k行,看当前高度有多少满足条件的子矩形

  •  由于我们知道第 k 行到第 i 行「每一行第 j 列向左延伸连续 1 的个数」 row[k][j],row[k+1][j],⋯,row[i][j],因此我们可以知道第 k 行满足条件的子矩形个数就是这些值的最小值它代表了「第 k 行到第 ii 行子矩形的宽的最大值」,公式化来说,即:
    在这里插入图片描述

  •  因此我们倒序枚举 k,用num 变量来记录到当前行 i 的最小值,即能在O(n) 的时间内统计出以 (i,j)为右下角满足条件的子矩形个数
    在这里插入图片描述

  •  举个例子吧,如下图的矩阵,我们现在计算以点mat[3][2]为右下角所构成的矩阵中子矩阵全为1的子矩阵的个数。

[0,0,1]
[0,1,1]
[1,1,1]
[1,1,1]
  •  首先是第四行,dp[3][2] = 3,所以最小长度为3,所以sum += 3,这里计算的矩阵是只有第四行元素构成的矩阵,如下所示:
[1,1,1],   [1,1],   [1]
  •  向上遍历,第三行时,dp[2][2] = 3,最小长度依然为3,sum += 3,这里计算的矩阵是第三、四行元素构成的矩阵,如下所示:
[1]    [1,1]    [1,1,1]
[1],   [1,1],   [1,1,1]
  •  继续向上遍历,第二行时,dp[1][2] = 2,此时的最小长度变为2,sum += 2,这里计算的矩阵是第二、三、四行元素构成的矩阵,如下所示:
[1]    [1][1]
[1]    [1][1]
[1],   [1][1]
  •  继续向上遍历,第一行时,dp[0][2] = 1,此时的最小长度变为1,sum += 1,这里计算的矩阵是第一、二、三、四行元素构成的矩阵,如下所示:
[1]
[1]
[1]
[1]
  •  该点遍历结束,继续循环遍历所有节点后返回sum即可

三、代码

枚举方法的代码

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        if(mat.empty())
        {
            return 0;
        }

        int m = (int)mat.size();
        int n = (int)mat[0].size();

        //dp[i][j]代表以i,j坐标为右端点,向左延续连续1的个数。意思是在第i行,j为终点,从j
        //向左连续1的个数,注意是连续连续连续
        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];
                }
                //如果当前位置为1,就代表可以在左边的基础上进行+1
                else if(mat[i][j] == 1)
                {
                    dp[i][j] = dp[i][j - 1] + 1;
                }
                //如果当前位置为0,那么dp代表的是连续1的个数,中间断了,直接赋值为0
                else 
                {
                    dp[i][j] = 0;
                }
            }
        }

        //保存最后的结果
        int sum = 0;

        //遍历,每次求以i,j坐标为右下角
        for(int i = 0;i < m;i++)
        {
            for(int j = 0;j < n;j++)
            {
                //保存点i,j坐标处向左延续连续1的个数
                int num = dp[i][j];

                //向上枚举每一行
                for(int k = i;k >= 0;k--)
                {
                    //一旦某一行为0,那么求min后都为0,代表没有构成矩阵
                    if(num == 0)
                    {
                        break;
                    }
                    //更新结果
                    num = min(num,dp[k][j]);
                    sum += num;
                }
            }
        }
        return sum;
    }
};
0

评论区