計算矩形的面積以及矩形內數字的總和-簡化版

# 計算每一行的最大矩形面積
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 = stack.pop()
            width = (index - stack[-1] - 1) if stack else index
            max_area = max(max_area, heights[top] * width)
    
    # 清空堆疊時的處理
    while stack:
        top = stack.pop()
        width = (index - stack[-1] - 1) if stack else index
        max_area = max(max_area, heights[top] * width)
    
    return max_area

# 找到最大矩形面積及矩形內的數值總和
def find_max_rectangle(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):
        # 更新每列的高度，只累加1和2的高度
        for col in range(cols):
            if grid[row][col] in (1, 2):
                heights[col] += 1
            else:
                heights[col] = 0  # 如果是0，重置該列高度
        
        # 計算當前行的最大矩形面積
        current_area = largest_histogram_area(heights)
        if current_area > max_area:
            max_area = current_area
            # 計算當前矩形內的數值總和
            total_sum = 0
            for i in range(row + 1 - max(heights), row + 1):
                for j in range(cols):
                    if grid[i][j] in (1, 2):
                        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(grid)
print("最大矩形面積:", max_area)
print("矩形內數值總和:", max_sum)

簡化的重點：

1. 高度更新：每一行的「1」和「2」累積成直方圖的高度，遇到「0」就重置為 0。
2. 最大矩形面積：使用堆疊來快速計算每一行的最大矩形面積。
3. 矩形內的數值總和：當找到最大矩形時，遍歷該矩形範圍內的數字，計算它們的總和。

輸出結果：

最大矩形面積: 4
矩形內數值總和: 6