求完善largest_at_position函数：计算指定左上角的最大矩形面积

我在实现largest_at_position函数时遇到困难，该函数需返回矩阵中以(row, col)为左上角的最大矩形面积，必须使用longest_chain辅助函数，且不能修改输入矩阵。当前我的代码仅能提取从起始列到行尾的所有数值，无法计算所有可能的矩形面积。

函数定义 #

目标函数 #

def largest_at_position(matrix: list[list[int]], row: int, col: int) -> int:
    '''
    返回矩阵中以<row>, <col>为左上角的最大矩形的面积。
    必须在遍历矩阵行时使用辅助函数<longest_chain>，不得修改输入矩阵。
    
    >>> case1 = [[1, 0, 1, 0, 0],
    ...          [1, 0, 1, 1, 1],
    ...          [1, 1, 1, 1, 1],
    ...          [1, 0, 0, 1, 0]]
    >>> largest_at_position(case1, 0, 0)
    4
    >>> largest_at_position(case1, 2, 0)
    5
    >>> largest_at_position(case1, 1, 2)
    6
    '''

辅助函数 #

from typing import List

def longest_chain(lst: List[int]) -> int:
    chain = 0
    lst2 = lst.copy()
    while chain < len(lst) and lst2[0] == 1:
        chain += 1
        lst2.pop(0)
    return chain

当前代码 #

def largest_at_position(matrix, row, col):
  nlist = []
  columns = len(matrix[0])
  i = row
  chain = longest_chain(matrix[i])
  
  while i < len(matrix):
    for j in range(col, columns):
      nlist.append(matrix[i][j])
    i += 1
  #nlist = nlist[::columns]
  return nlist

解决方案 #

实现思路 #

1. 从指定起始行开始逐行向下遍历，每一行提取从起始列开始的子列表
2. 用longest_chain获取当前行从起始列开始的连续1的长度（即该行能作为矩形右边界的最大宽度）
3. 维护当前遍历过的所有行中的最小连续宽度（因为矩形的宽度受限于最窄的那一行）
4. 计算以当前行为底边的矩形面积（最小宽度 × 遍历过的行数），并更新最大面积
5. 若某行的连续1长度为0，说明无法继续向下形成连续矩形，直接终止遍历

完整代码 #

from typing import List

def longest_chain(lst: List[int]) -> int:
    chain = 0
    lst2 = lst.copy()
    while chain < len(lst) and lst2[0] == 1:
        chain += 1
        lst2.pop(0)
    return chain

def largest_at_position(matrix: list[list[int]], row: int, col: int) -> int:
    max_area = 0
    current_min_width = float('inf')
    rows = len(matrix)
    # 从起始行开始遍历每一行
    for i in range(row, rows):
        # 提取当前行从col开始的子列表，不修改原矩阵
        current_segment = matrix[i][col:]
        width = longest_chain(current_segment)
        # 如果当前行起始位置是0，无法形成连续矩形，直接退出循环
        if width == 0:
            break
        # 更新当前最小宽度
        current_min_width = min(current_min_width, width)
        # 计算当前矩形面积：宽度 × 高度（遍历过的行数）
        current_area = current_min_width * (i - row + 1)
        if current_area > max_area:
            max_area = current_area
    return max_area

# 测试示例
case1 = [[1, 0, 1, 0, 0],
         [1, 0, 1, 1, 1],
         [1, 1, 1, 1, 1],
         [1, 0, 0, 1, 0]]
print(largest_at_position(case1, 0, 0))  # 输出4
print(largest_at_position(case1, 2, 0))  # 输出5
print(largest_at_position(case1, 1, 2))  # 输出6

代码说明 #

• 不修改输入矩阵：通过切片matrix[i][col:]获取子列表，原矩阵保持不变
• 强制使用longest_chain：每一行的连续1长度都通过该辅助函数计算
• 正确计算所有可能的矩形：通过维护current_min_width，确保每一步计算的是当前能形成的最大矩形面积，遍历过程中不断更新最大值

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