求二维网格中可放置的最大矩形桌面积问题求助

Hey there! 这个问题其实就是经典「最大矩形面积」问题的实际应用——咱们要找的就是网格里由连续1组成的最大矩形区域，用来放最大的办公桌对吧？下面我给你拆解清楚思路和可运行的代码：

核心思路 #

咱们可以把这个二维网格转换成一系列直方图来处理，步骤很清晰：

• 构建高度数组：对于每一行来说，每个位置的高度是「从当前行往上（包括当前行）连续的1的数量」。如果当前格子是0，那这个位置的高度直接重置为0。
• 计算直方图最大面积：对每一行对应的高度数组，用单调栈计算这个直方图能容纳的最大矩形面积。把所有行的结果取最大值，就是咱们要的最大办公桌面积。

这种方法的时间复杂度是O(m*n)（m是行数，n是列数），完全能处理总元素数≤1e6的约束条件。

代码实现 #

这里用Python写了biggestTable函数，直接传入grid就能得到结果：

def biggestTable(grid):
    if not grid or not grid[0]:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    heights = [0] * cols
    max_area = 0
    
    for row in grid:
        # 更新当前行的高度数组：遇到1累加，遇到0重置
        for col in range(cols):
            heights[col] = heights[col] + 1 if row[col] == 1 else 0
        
        # 用单调栈计算当前直方图的最大面积
        stack = []
        # 在高度数组末尾加个0，确保栈里所有元素都能被处理到
        temp_heights = heights + [0]
        for i in range(len(temp_heights)):
            # 当当前高度小于栈顶索引对应的高度时，弹出栈顶计算面积
            while stack and temp_heights[i] < temp_heights[stack[-1]]:
                current_height = temp_heights[stack.pop()]
                # 计算宽度：栈空则宽度为当前索引，否则是当前索引到新栈顶的距离减1
                current_width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, current_height * current_width)
            stack.append(i)
    
    return max_area

代码关键点说明 #

• 高度数组更新：每一行遍历的时候，相当于把当前行作为直方图的基底，往上堆叠连续的1，这样就把二维问题转化成了多个一维直方图问题。
• 单调栈的作用：栈里始终维护着高度递增的索引序列，这样当遇到更矮的高度时，我们能快速确定以弹出元素为高度的矩形的左右边界，从而计算出最大面积。

输入处理示例 #

如果需要从标准输入读取题目给定格式的数据，可以加上这段代码：

# 读取输入
rows = int(input())
cols = int(input())
grid = []
for _ in range(rows):
    line = input().strip()
    grid.append([int(c) for c in line])

# 计算并输出结果
print(biggestTable(grid))

比如用题目里的原始输入示例测试：

4
5
11110
11010
11000
00000
运行后会输出4，对应第一行前四个连续的1组成的矩形。

而题目里的另一个示例输入[[1, 0, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]，函数会返回9，也就是右上方3x3的连续1区域。

内容的提问来源于stack exchange，提问作者mohamed nageh