1504. Count Submatrices With All Ones

题目信息

题号:

1504

难度:

Medium

主题:

二进制矩阵、动态规划、单调栈

原题:

LeetCode 1504

重点:

统计由连续行和连续列组成、且所有元素均为 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
解释:唯一非空子矩阵包含零。