# 1504. Count Submatrices With All Ones
###### tags: `Leetcode` `Medium` `Stack`
Link: https://leetcode.com/problems/count-submatrices-with-all-ones/
## 思路
思路[参考](https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack)
### 思路一 Brute Force $O(MMN)$ $O(MN)$
### 思路二 Stack $O(MN)$ $O(MN)$
和[0084. Largest Rectangle in Histogram](https://hackmd.io/dE8-j_vvRq-zByLqRb7z7g)思路有点像

given this 我们用单调栈算出加上这行 结果又多了多少rectangle
算的方法参考[这里](https://leetcode.com/problems/count-submatrices-with-all-ones/solutions/720265/java-detailed-explanation-from-o-mnm-to-o-mn-by-using-stack/)
![](https://i.imgur.com/2Ud9mBh.png)
## Code
### 思路一 Brute Force $O(MMN)$ $O(MN)$

class Solution {
public int numSubmat(int[][] mat) {
int M = mat.length, N = mat[0].length;
int res = 0;
for(int up = 0; up < M; up++){
int[] h = new int[N];
Arrays.fill(h, 1);
for(int down = up; down < M; down++){
for(int i = 0; i < N; i++) h[i] &= mat[down][i];
res += countOneRow(h);
}
}
return res;
}
private int countOneRow(int[] h){
int cnt = 0, length = 0;
for(int i=0; i<h.length; i++){
length = h[i]==0 ? 0 : length+1;
cnt += length;
}
return cnt;
}
}

### 思路二 Stack $O(MN)$ $O(MN)$

class Solution:
def numSubmat(self, mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
h = [0]*n
ans = 0

def helper():
matricesSum = [0]*n
stack = []
for i in range(n):
while stack and h[stack[-1]]>h[i]:
stack.pop()
if not stack:
matricesSum[i] = (i+1)*h[i]
else:
matricesSum[i] = matricesSum[stack[-1]]
matricesSum[i] += h[i]*(i-stack[-1])
stack.append(i)
return sum(matricesSum)

for i in range(m):
for j in range(n):
h[j] = 0 if mat[i][j]==0 else h[j]+1
ans += helper()
return ans

class Solution {
public int numSubmat(int[][] mat) {
int M = mat.length, N = mat[0].length;
int res = 0;
int[] h = new int[N];
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
h[j] = mat[i][j]==0?0:h[j]+1;
}
res += helper(h);
}
return res;
}
private int helper(int[] h){
int[] sum = new int[h.length];
Stack<Integer> stack = new Stack<>();

for(int i=0; i<h.length; i++){
while(!stack.isEmpty() && h[stack.peek()]>=h[i]) stack.pop();
if(stack.isEmpty()){
sum[i] = (i+1)*h[i];
}
else{
int preIdx = stack.peek();
sum[i] = sum[preIdx];
sum[i] += (i-preIdx)*h[i];
}
stack.push(i);
}
int res = 0;
for(int s:sum) res += s;
return res;
}
}