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

 如果不使用堆疊來解決這個問題，程式的邏輯會稍微簡單一些，但運行效率會較低。我們可以直接使用兩層迴圈來計算每一行的高度，並在每次更新後嘗試找出當前行的最大矩形。

簡化版程式碼（不使用堆疊）：

# 計算最大矩形面積及矩形內的數值總和
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，重置該列高度

        # 直接遍歷每一個左上角起點，找到每個可能的矩形
        for start_col in range(cols):
            if heights[start_col] == 0:
                continue
            min_height = heights[start_col]
            for end_col in range(start_col, cols):
                if heights[end_col] == 0:
                    break
                min_height = min(min_height, heights[end_col])
                current_area = min_height * (end_col - start_col + 1)
                
                if current_area > max_area:
                    max_area = current_area
                    # 計算當前矩形內的數值總和
                    total_sum = 0
                    for i in range(row - min_height + 1, row + 1):
                        for j in range(start_col, end_col + 1):
                            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」則高度歸零。
2. 最大矩形計算：使用雙重迴圈遍歷每個矩形的起點，從每一列開始，往右擴展，並且在過程中持續更新矩形的最小高度，來計算可能的最大面積。
3. 矩形內的數值總和：每當發現新的最大矩形時，遍歷這個矩形的範圍，計算矩形內的數值總和。

輸出結果：

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