1504. Count Submatrices With All Ones¶
题目信息¶
- 题号:
1504
- 难度:
Medium
- 主题:
二进制矩阵、动态规划、单调栈
- 原题:
- 重点:
统计由连续行和连续列组成、且所有元素均为
1的非空矩形子矩阵数量
题目重述¶
给定只包含 0 和 1 的矩阵 mat。子矩阵必须由一段连续行和一段连续列的交集构成。
请返回元素全部为 1 的非空子矩阵总数。不同边界的矩形分别计数,即使它们互相重叠。
1 <= mat.length, mat[i].length <= 150,每个元素为 0 或 1。
自建示例¶
不同形状和大小的全一矩形都要计数:
输入:mat = [[1,1],[1,1]]
输出:9
解释:共有四个 1 x 1、两个 1 x 2、两个 2 x 1 和一个 2 x 2 子矩阵。
没有值为一的格子时答案为零:
输入:mat = [[0]]
输出:0
解释:唯一非空子矩阵包含零。