LeetCode -- 1504. Count Submatrices With All Ones 計數全為1的子矩陣

Description

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

給定一個 m x n 二進位矩陣 mat ，傳回全為 1 的子矩陣的數量。

Solution

這邊我會分享三種方法。其中第一種，邏輯雖然正確，但因為時間複雜度為 O(k² × m × n) (k=1的數量)，所以會 Time Limit Exceeded。分享出來單純是為了記錄。

Coordinate transformation (座標化)

concept：Every rectangle has a top-left and bottom-right corner, so we can extract the coordinates of all the 1s and then check whether the rectangle formed by any two points contains any 0s. However, it's important to note that we only check rectangles defined by the top-left and bottom-right points—otherwise, we risk counting duplicates.

概念：所有的矩形都有左上和右下，因此我們可以將所有 1 的座標取出來，接著檢查兩個點所圍矩形裡有沒有 0。不過需要注意，我們只檢查左上和右下點圍出來的矩形，不然會重複計算。

program

import numpy as np
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        height = len(mat)
        weight = len(mat[0])
        one = []

        for i in range(height):
            for j in range(weight):
                if mat[i][j] == 1:
                    one.append([i,j])
        answer = len(one)

        mat = np.array(mat)
        for i in range(len(one)):
            for j in range(i+1,len(one)):
                if one[i][0] <= one[j][0] and one[i][1] <= one[j][1]:
                    if 0 not in mat[one[i][0]:one[j][0]+1, one[i][1]:one[j][1]+1]:
                        answer += 1

        return answer

Enumeration (枚舉)

For a given row, if we add each element to the one before it, each value becomes the width of a potential rectangle. For example, the row 0111 would transform into 0123. At this point, by looking upward from the current row, we can identify rectangles of size X × Y—as illustrated in the diagram below.

對於一個 row，如果將每一元素加上前一個元素，那每個元素就會變成矩形的寬度。舉個例子，0111 會變成 0123。此時，如果我們往上找就可以得到 X x Y 的矩形。如下圖所示

program：

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        res = 0
        row = [[0] * n for _ in range(m)]
        sum = 0
        for i in range(m):
            for j in range(n):
                if j == 0:
                    row[i][j] = mat[i][j]
                elif mat[i][j] == 0:
                    continue
                else:
                    row[i][j] = row[i][j-1]+1 # +1：row[i][j]
                cur = row[i][j]
                for k in range(0,i+1):
                    if row[i-k][j] == 0:
                        break                    
                    cur = min(cur, row[i-k][j])
                    sum += cur
        return sum

Monotonic stack (單調堆疊)

First, we initialize a list to store the heights, starting with [0] * len(mat[0]). The first thing we do is increment the value at each index where the current cell is 1. This way, we record the height of consecutive 1s ending at that index for the current row.

For example, given ([0,1,1], [1,1,0]), when we process the second row, the height list becomes [1,2,0].

首先，我們有一個存儲高度的串列，初始為 0 * len(mat[0])。因此，我們第一件要做的事是將為 1 的加一，以此紀錄目前該 row 該 index 為底的高度，ex：([0,1,1][1,1,0]) 當遍歷到第二層 row 時 -> ([1,2,0])。

Next, we use a stack that stores three pieces of information: index, count, and height. This stack is updated once per row, just like the height list is refreshed at the end of each row.

There's a key concept readers need to understand: although we store information for every element, we must perform a crucial step before pushing new data. If the current height is not greater than the top of the stack, we remove all previous entries with a height taller than the current one. This ensures that when we calculate the area of an X × Y rectangle, we can correctly include all valid submatrices.

If this explanation feels a bit abstract, you can refer to the formula in the code:

prev + (i - j) * h

Here:

• prev is the count from the previous stack entry (equivalent to stack[j][1])
• i is the current index
• j is the index of the previous entry
• h is the height of that entry

If it still feels unclear, the diagram below should help clarify the concept visually.

接著，我們有一個 stack。這個 stack 負責儲存三項資訊：index, count, height，並且每行會更新一次，就像高度串列每行結束後會全部更新完一樣。然後有個重要的概念讀者必須知道，雖然我們會將每個元素的資訊都儲存起來，但在存儲之前，我們要做一項非常重要的動作。當目前高度並非 stack 裡最高時，程式碼會去刪除前面比目前高度還要高的資訊，如此一來可以保證，當我們在計算 XxY 矩形時可以涵括到每一個。如果覺得這樣講有點抽象可以搭配程式碼中的這項公式 prev + (i - j) * h 來看。prev 是前一項的 count，也可以想成 stack[j][1]；i 為當前 index；j 為前一項的 index；h 為該項的高度。如果還是覺得抽象，可以參考下方圖片。

program：

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        height = [0] * len(mat[0])
        res = 0
        for row in mat:
            for i, x in enumerate(row):
                height[i] = 0 if x==0 else height[i] + 1
            stack = [[-1,0,-1]]
            for i, h in enumerate(height): 
                while stack[-1][2] >= h:
                    stack.pop()
                j, prev, _ = stack[-1]
                cur = prev + (i-j)*h
                stack.append([i,cur,h])
                res += cur
        return res