> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/stack/wei-chi-di-zeng-huo-di-jian/largest-rectangle-in-histogram/1504.-count-submatrices-with-all-ones.md).

# 1504. Count Submatrices With All Ones

https\://leetcode.com/problems/count-submatrices-with-all-ones/

Given a `rows * columns` matrix `mat` of ones and zeros, return how many **submatrices** have all ones.

**Example 1:**

```
Input: mat = [[1,0,1],
              [1,1,0],
              [1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
```

**Example 2:**

```
Input: mat = [[0,1,1,0],
              [0,1,1,1],
              [1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
```

**Example 3:**

```
Input: mat = [[1,1,1,1,1,1]]
Output: 21
```

**Example 4:**

```
Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5
```

由01组成的矩阵，问其中有多少个由1组成的长方形。矩阵 + count => DP。遍历到(i, j), 如下图

![](https://pic1.zhimg.com/80/v2-9cc25475845142b0f1fbdb364cf882d4_1440w.jpg)

观察到新引入的长方形分别是在第i行到(i, j)连着的1，长度4对应个数4；i和i-1行能拼成的长方形长度3，额外长方形个数3；依此类推，长度一但缩短，之后遍历能拼成的长方形长度最长只能到缩短后的长度，最后对应4 + 3 + 2 + 2。也就是从i行往上遍历，k in \[i, 0]，第k行从左到j最长连续1的个数的dp\[k]\[j]，mi位当前遍历到的最短长度，mi=min(mi, dp\[k]\[j])，res += mi。

```python
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        s, res = [], 0
        heights.append(0)
        for i, h in enumerate(heights):
            while len(s) > 0 and h < heights[s[-1]]:
                hei = heights[s[-1]]
                s.pop()
                wid = i - s[-1] - 1 if len(s) > 0 else i
                res = max(res, hei * wid)
            s.append(i)
        return res
```

进一步，将一整行看作是有不同高度的histogram，这一行对应新增加的长方形为histogram能形成的长方形数目，从左往右以每一列为底的新长方形数目如图：

![](https://pic4.zhimg.com/80/v2-e7bbc8432e6c1b1e72b7aaed312c6a6f_1440w.jpg)

和上个解法同理，从右往左遍历k in \[j, 0]，mi为当前遍历的最短高度，res += mi(k) for all k。此时如果能统计出以heights\[j]向左最远能到的位置如peek，再加上peek前的结果也就是对j列所求。比如图中最后一列(2+2+2 + 3)前面三个2为之前第3列所求，最后的3为当前列的高度\*它对应的宽度1。让dp\[k]记录第k列所增加的新长方形数目。求最远能扩所少想起Largest Rectangle in Histogram，类似的按高度递增的stack内记录index，不同在于这次宽度不是对每个弹出的元素做计算，而是所有弹出后计算i和peek的diff：

![](https://pic1.zhimg.com/80/v2-1a32f2c0d217a4e98cd05709327a8678_1440w.jpg)

思路和代码参考自[这](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O%28MNM%29-to-O%28MN%29-by-using-Stack)。

```python
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M, N, res = len(mat), len(mat[0]), 0
        height = [0] * N
        def level(height: []):
            stack, res, dp = [], 0, [0] * N
            for i, h in enumerate(height):
                while len(stack) > 0 and h < height[stack[-1]]: stack.pop()
                if len(stack) > 0:
                    dp[i] = dp[stack[-1]]
                    dp[i] += h * (i - stack[-1]) 
                else: dp[i] = h * (i + 1)
                stack.append(i)
            res = sum(dp)
            return res
            
        for i in range(M):
            for j in range(N): 
                height[j] = height[j] + 1 if mat[i][j] == 1 else 0
            res += level(height)
        return res
        
```