> 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

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
        
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET 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?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.