leetcode1504. 統計全 1 子矩形

給你一個只包含 0 和 1 的 rows * columns 矩陣 mat ，請你返回有多少個 子矩形 的元素全部都是 1 。

示例 1：

輸入：mat = [[1,0,1],[1,1,0],[1,1,0]] 輸出：13 解釋： 有 6 個 1x1 的矩形。 有 2 個 1x2 的矩形。 有 3 個 2x1 的矩形。 有 1 個 2x2 的矩形。 有 1 個 3x1 的矩形。 矩形數目總共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

輸入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]] 輸出：24 解釋： 有 8 個 1x1 的子矩形。 有 5 個 1x2 的子矩形。 有 2 個 1x3 的子矩形。 有 4 個 2x1 的子矩形。 有 2 個 2x2 的子矩形。 有 2 個 3x1 的子矩形。 有 1 個 3x2 的子矩形。 矩形數目總共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

示例 3：

輸入：mat = [[1,1,1,1,1,1]] 輸出：21

示例 4：

輸入：mat = [[1,0,1],[0,1,0],[1,0,1]] 輸出：5

提示：

• 1 <= rows <= 150
• 1 <= columns <= 150
• 0 <= mat[i][j] <= 1

---

方法：動態規劃

思路：

本題的暴力思路就是枚舉所有的矩形（左上角坐標和右下角坐標），然后計算這個矩形內是不是都為1；但是這樣枚舉的時間復雜度就是O(N ^ 4)，計算矩形內部是不是都為1最多需要O(N ^ 2)，有太多的重復計算，我們需要使用動態規劃來解決。

我們設dp數組為二維，dp(i,j)表示(i,j)這個點（包括該點）該行左邊連續的1的個數。我們計算這個的目的是這樣的，如果以(i,j)為矩形的右下角，那么高為1的那滿足條件的矩形個數就為dp(i,j)，如下圖所示：

我們計算出所有的dp之后，我們使用兩層循環來遍歷所有的點，計算以這個點為右下角的矩形有多少個。以該點(i,j)為例，以(i,j)為右下角，高度為1的矩形個數為dp(i,j)；我們還需要向上遍歷，來計算以該點(i,j)為右下角，高度為2、3、4...的矩形有多少個。

當遍歷到上一行時，dp(i-1,j)表示(i-1,j)左邊連續1的個數，因為要構成兩層的矩形，矩形中都為1；所以可以構成的矩形的數量為：min(dp(i,j),dp(i-1,j))，我們維護這個數，這個數表示這兩層共有的都為1的寬度，繼續向上遍歷，更新這個寬度，找到高度為3、4、5...的矩形。

遍歷所有的位置，計算它為右下角的矩形個數，返回總數。

代碼：

class Solution:def numSubmat(self, mat: List[List[int]]) -> int:rows = len(mat)cols = len(mat[0])dp = [[0 for _ in range(cols)] for _ in range(rows)]#dp[i][j]表示第i行，從j開始往左數連續有多少個1for i in range(rows):for j in range(cols):if mat[i][j]:dp[i][j] = dp[i][j-1] + 1 if j > 0 else 1res = 0#遍歷每個位置，以這個位置為矩形右下角for i in range(rows):for j in range(cols):#leftnum維護可以構成矩形的最大寬度leftnum = float('inf')#從(i,j)開始向上遍歷，對于第i行，求出dp(i,j)表示(i,j)左邊的連續1個數#也就是以(i,j)為右下角，高為1，的矩形個數(一個長度對應一個矩形)#遍歷到i-1行的時候，更新leftnum，表示第i行和第i-1行從j往左的連續1的個數的#較小值，這就是以(i,j)為右下角，高為2的矩形個數#遍歷i上面的所有行，找到所有的(i,j)為右下角，高度分別為1,2,3...，i+1的矩形for k in range(i,-1,-1):leftnum = min(leftnum,dp[k][j])#如果某一行更新后，leftnum為0，那么上面的行就不用看了，break跳出if leftnum == 0:breakres += leftnumreturn res

結果：

總結

以上是生活随笔為你收集整理的jq遍历子元素_leetcode第196周赛第三题统计全 1 子矩形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。