計算矩形的面積以及矩形內數字的總和。

 

解題目標：

在一個只包含「0」、「1」、「2」的二維矩陣中，找到只由「1」和「2」組成、且不包含「0」的最大矩形。接著，計算這個矩形的面積以及矩形內數字的總和。

解題步驟：

1. 將矩陣轉換成直方圖：

   • 我們從矩陣的每一行開始，計算每一列中「1」和「2」的連續高度（代表連續出現「1」或「2」的次數）。
   • 如果遇到「0」，那一列的高度就變為 0，因為「0」不能包含在矩形中。

2. 逐行計算最大矩形：

   • 對於每一行（直方圖），我們嘗試找到基於當前行形成的最大矩形面積。
   • 我們使用一個「堆疊」的資料結構來幫助計算每一行的最大矩形，這樣可以更快速地找到矩形的面積。

3. 計算矩形內的數值總和：

   • 當找到一個有效的最大矩形時，我們會計算這個矩形內所有「1」和「2」的數值總和。

4. 更新結果：

   • 不斷更新我們發現的最大矩形面積和總和，直到我們檢查完所有行的高度。

簡化示例：

假設有一個矩陣如下：

[
    [0, 2, 0, 1, 2],
    [0, 1, 1, 0, 0],
    [2, 0, 2, 1, 1],
    [0, 0, 1, 2, 0],
]

步驟：

1. 第一行：找到每列的高度為 [0, 1, 0, 1, 1]。
2. 第二行：計算後得到高度為 [0, 2, 2, 0, 0]，其中最大矩形面積是 4。
3. 總和：找到這個矩形後，計算它內部的數字總和，得到總和為 6。

最終結果：

• 最大矩形面積：4
• 矩形內的數字總和：6

這樣的方式，可以有效地找到包含「1」和「2」的最大矩形，並計算相關數據。這是運用高度累加和最大矩形面積演算法解決問題的簡單思路。

計算直方圖中的最大矩形面積

def largest_histogram_area(heights):
stack = []
max_area = 0
index = 0

while index < len(heights):
    if not stack or heights[index] >= heights[stack[-1]]:
        stack.append(index)
        index += 1
    else:
        top_of_stack = stack.pop()
        area = (heights[top_of_stack] *
                ((index - stack[-1] - 1) if stack else index))
        max_area = max(max_area, area)

while stack:
    top_of_stack = stack.pop()
    area = (heights[top_of_stack] *
            ((index - stack[-1] - 1) if stack else index))
    max_area = max(max_area, area)

return max_area

計算最大矩形面積及其包含值的總和

def find_max_rectangle_with_sum(grid):
if not grid:
return 0, 0

rows = len(grid)
cols = len(grid[0])

heights = [0] * cols
max_area = 0
max_sum = 0

for row in range(rows):
    for col in range(cols):
        if grid[row][col] in (1, 2):
            heights[col] += 1
        else:
            heights[col] = 0
    
    # 使用堆疊來計算最大矩形面積及其對應的總和
    stack = []
    index = 0
    while index < len(heights):
        if not stack or heights[index] >= heights[stack[-1]]:
            stack.append(index)
            index += 1
        else:
            top_of_stack = stack.pop()
            width = (index - stack[-1] - 1) if stack else index
            area = heights[top_of_stack] * width
            if area > max_area:
                max_area = area
                # 計算矩形內的值總和
                total_sum = 0
                for i in range(row - heights[top_of_stack] + 1, row + 1):
                    for j in range(stack[-1] + 1 if stack else 0, index):
                        total_sum += grid[i][j]
                max_sum = total_sum

return max_area, max_sum

測試資料

grid = [
[0, 2, 0, 1, 2],
[0, 1, 1, 0, 0],
[2, 0, 2, 1, 1],
[0, 0, 1, 2, 0],
]

呼叫函式，計算最大矩形的面積及其值總和

max_area, max_sum = find_max_rectangle_with_sum(grid)