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), 如下图

观察到新引入的长方形分别是在第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。

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能形成的长方形数目，从左往右以每一列为底的新长方形数目如图：

和上个解法同理，从右往左遍历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：

思路和代码参考自这。

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