1.題目基本信息

1.1.題目描述

給你一個 m x n 的二進制矩陣 mat ，請你返回有多少個 子矩形 的元素全部都是 1 。

1.2.題目地址

https://leetcode.cn/problems/count-submatrices-with-all-ones/description/

2.解題方法

2.1.解題思路

單調棧

時間復雜度：O(n)

2.2.解題步驟

第一步，構建rows矩陣，rows[i][j]表示從mat[i][j]開始向左連續為1的個數（包括本身）

第二步，遍歷每一列，列號記為j，再遍歷每列中的每行，行號即為i

2.1.構建每一列的維護變量。total維護以(i,j)為右下角的全為1的子矩陣個數（如果該列的rows[i][j]非嚴格遞增，則就等于前綴和）；stack維護隨著rows[i][j]嚴格遞增的單調棧，存儲單元形式為(rows[i][j],height*=rows矩陣中(i,j)上面連續不小于rows[i][j]的個數+1)

2.2.遍歷每一列，更新total和stack，并將total更新到結果變量result中。total更新：如果rows[i][j]大于或等于單調棧棧頂的元素，則直接將rows[i][j]增加到total中，并入棧即可；如果小于，則將大的元素從棧中彈出，并從total中切除多余的子矩陣數（相當于切成一個非嚴格遞增的rows[i][j]序列）

3.解題代碼

Python代碼

class Solution:def numSubmat(self, mat: List[List[int]]) -> int:# 思路：單調棧m, n = len(mat), len(mat[0])# 第一步，構建rows矩陣，rows[i][j]表示從mat[i][j]開始向左連續為1的個數（包括本身）rows = [[0] * n for _ in range(m)]for i in range(m):for j in range(n):if mat[i][j] == 1:if j > 0:rows[i][j] = rows[i][j - 1] + 1else:rows[i][j] = 1# 第二步，遍歷每一列，列號記為j，再遍歷每列中的每行，行號即為iresult = 0for j in range(n):# 2.1.構建每一列的維護變量。total維護以(i,j)為右下角的全為1的子矩陣個數（如果該列的rows[i][j]非嚴格遞增，則就等于前綴和）；stack維護隨著rows[i][j]嚴格遞增的單調棧，存儲單元形式為(rows[i][j],height*=rows矩陣中(i,j)上面連續不小于rows[i][j]的個數+1)total = 0stack = []# 2.2.遍歷每一列，更新total和stack，并將total更新到結果變量result中。total更新：如果rows[i][j]大于或等于單調棧棧頂的元素，則直接將rows[i][j]增加到total中，并入棧即可；如果小于，則將大的元素從棧中彈出，并從total中切除多余的子矩陣數（相當于切成一個非嚴格遞增的rows[i][j]序列）for i in range(m):height = 1while stack and stack[-1][0] >= rows[i][j]:preRow, preHeight = stack.pop()height += preHeighttotal -= (preRow - rows[i][j]) * preHeighttotal += rows[i][j]stack.append([rows[i][j], height])result += totalreturn result

4.執行結果