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
Constraints:
1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # 这道题是问有多少个submatrices有all ones
        # 和84Largest Rectangle in Histogram很像
         
        # 解法1 - 枚举右下角
        m, n = len(mat), len(mat[0])
        left_ones = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    left_ones[i][j] = 0
                else:
                    left_ones[i][j] = 1
                    if j > 0:
                        left_ones[i][j] += left_ones[i][j - 1]
        
#         res = 0
#         for i in range(m):
#             for j in range(n):
#                 curr_left_ones = left_ones[i][j]
#                 for k in range(i, -1, -1):
#                     curr_left_ones = min(curr_left_ones, left_ones[k][j])
#                     res += curr_left_ones
        
#         return res


        ans = 0
        for j in range(n):
            Q = list()
            total = 0
            for i in range(m):
                height = 1
                while Q and Q[-1][0] > left_ones[i][j]:
                    # 弹出的时候要减去多于的答案
                    total -= Q[-1][1] * (Q[-1][0] - left_ones[i][j])
                    height += Q[-1][1]
                    Q.pop()
                total += left_ones[i][j]
                ans += total
                Q.append((left_ones[i][j], height))

        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # 这道题是问有多少个submatrices有all ones
        # 和84Largest Rectangle in Histogram很像
         
        # 解法1 - 枚举右下角
        m, n = len(mat), len(mat[0])
        left_ones = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    left_ones[i][j] = 0
                else:
                    left_ones[i][j] = 1
                    if j > 0:
                        left_ones[i][j] += left_ones[i][j - 1]
        
#         res = 0
#         for i in range(m):
#             for j in range(n):
#                 curr_left_ones = left_ones[i][j]
#                 for k in range(i, -1, -1):
#                     curr_left_ones = min(curr_left_ones, left_ones[k][j])
#                     res += curr_left_ones
        
#         return res


        ans = 0
        for j in range(n):
            Q = list()
            total = 0
            for i in range(m):
                height = 1
                while Q and Q[-1][0] > left_ones[i][j]:
                    # 弹出的时候要减去多于的答案
                    total -= Q[-1][1] * (Q[-1][0] - left_ones[i][j])
                    height += Q[-1][1]
                    Q.pop()
                total += left_ones[i][j]
                ans += total
                Q.append((left_ones[i][j], height))

        return ans

