1.題目基本信息

1.1.題目描述

給定一個大小為 m x n 的二維矩陣 grid。同時給定一個 非負整數 k。

返回滿足下列條件的 grid 的子矩陣數量：

子矩陣中最大的元素 小于等于 k。

子矩陣的每一行都以 非遞增 順序排序。

矩陣的子矩陣 (x1, y1, x2, y2) 是通過選擇所有滿足 x1 <= x <= x2 且 y1 <= y <= y2 的 grid[x][y] 元素組成的矩陣。

1.2.題目地址

https://leetcode.cn/problems/find-sorted-submatrices-with-maximum-element-at-most-k/description/

2.解題方法

2.1.解題思路
單調棧

時間復雜度：O(n)

2.2.解題步驟
第一步，構建rows矩陣，rows[i][j]表示從mat[i][j]開始向左連續非嚴格遞增且小于等于k的元素的個數（包括本身）

第二步，遍歷每一列，列號記為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 countSubmatrices(self, grid: List[List[int]], k: int) -> int:# 思路：單調棧# 參考：Leetcode 1504. 統計全 1 子矩形mat = gridm, n = len(mat), len(mat[0])# 第一步，構建rows矩陣，rows[i][j]表示從mat[i][j]開始向左連續非嚴格遞增且小于等于l的元素的個數（包括本身）rows = [[0] * n for _ in range(m)]for i in range(m):for j in range(n):if mat[i][j] <= k:if j > 0 and mat[i][j] <= mat[i][j - 1]: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.執行結果