最大点函数

Question

很难找到以下函数的所有可能的矩形值。

def largest_at_position(matrix: list[list[int]], row: int, col: int) -> int:
    """
    Returns the area of the largest rectangle whose top left corner is at
    position <row>, <col> in <matrix>.

    You MUST make use of the helper <longest_chain> here as you loop through
    each row of the matrix. Do not modify (i.e., mutate) the input matrix.

    >>> 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
    """

这是最长链辅助函数的代码

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

Answer 1

一种可能的解决方案（保留仍形成矩形的行区域列表，然后在末尾对面积求和）：

def largest_at_position(matrix: list[list[int]], row: int, col: int) -> int:
    rv = []
    while row < len(matrix):
        row_area = longest_chain(matrix[row][col:])
        if row_area == 0:
            break
        elif not rv:
            rv.append(row_area)
        elif row_area >= rv[-1]:
            rv.append(min(row_area, rv[-1]))
        else:
            break
        row += 1
    return sum(rv)


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


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))
print(largest_at_position(case1, 2, 0))
print(largest_at_position(case1, 1, 2))

打印：

4
5
6