LeetCode 221最大正方形问题：卷积解法的性能优化求助

问题描述与思路 #

针对LeetCode第221题「最大正方形」（要求在二维二进制网格中寻找由1组成的最大正方形），我自行设计了一种基于卷积的思路：

• 使用尺寸为(1,1)、(2,2)…的全1核与输入数组卷积
• 标记卷积结果等于n²（n为核尺寸）的索引，这些索引对应全1正方形的左上角
• 用这些索引选择性地进行下一个尺寸(n+1,n+1)核的卷积（本质为Hadamard乘积）
• 重复上述步骤直到索引数量为1或0，以此确定最大正方形的尺寸

当前实现代码 #

from typing import List
import numpy as np

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        matrix = [[int(j) for j in i] for i in matrix]
        shap = np.shape(matrix)
        if np.array_equal(matrix, np.ones(shap)):
            return min(shap[0], shap[1]) ** 2
        # 生成从1到最大可能尺寸的序列
        max_possible = max(shap[0], shap[1])
        s = list(enumerate(range(1, max_possible + 1), start=1))
        indices = list(np.ndindex(shap))
        
        def convolution(m, k, ind):
            n = len(k)
            # 对矩阵进行填充
            m_padded = np.pad(m, [n, n], mode='constant')
            mm = np.copy(m_padded)
            # 遍历索引计算卷积值
            for i in ind:
                x, y = i
                sub_matrix = mm[x+1:x+1+n, y+1:y+1+n]
                m_padded[x+n, y+n] = np.sum(np.multiply(sub_matrix, k))
            # 筛选出卷积结果等于n²的索引
            rows, cols = np.where(m_padded == n**2)
            return [(rows[i]-n, cols[i]-n) for i in range(len(rows))]

        for size_idx, n in s:
            kernel = np.ones((n, n))
            indices = convolution(matrix, kernel, indices)
            if len(indices) == 1:
                return n ** 2
            elif len(indices) == 0:
                return (n - 1) ** 2
        return 0

性能问题 #

该方案可正常运行，但在最坏情况（如300x300全1矩阵）下耗时长达2分50秒，需要针对性优化性能。

优化建议 #

1. 替换手动卷积为Numpy/Scipy原生卷积操作 #

手动遍历索引计算卷积的效率极低，Python循环在处理大量数据时性能瓶颈明显。可以使用scipy.signal.convolve2d（支持二维卷积），其底层为优化过的C实现，能大幅提升计算速度：

from scipy.signal import convolve2d

# 替代手动卷积的逻辑
def check_square_size(matrix, n):
    kernel = np.ones((n, n))
    conv_result = convolve2d(matrix, kernel, mode='valid')
    # 存在等于n²的结果说明有n×n的全1正方形
    return np.any(conv_result == n**2)

2. 倒序遍历尺寸，提前终止 #

改为从最大可能的尺寸（min(行数,列数)）开始倒序尝试，一旦找到符合条件的正方形，直接返回结果，避免不必要的小尺寸计算：

max_size = min(shap[0], shap[1])
for n in range(max_size, 0, -1):
    if check_square_size(matrix, n):
        return n ** 2
return 0

3. 改用前缀和数组加速子矩阵求和 #

卷积的本质是计算子矩阵的和，使用前缀和数组可以将任意子矩阵的求和时间降低到O(1)，比卷积更高效：

def maximalSquare(self, matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    # 转换为整数矩阵
    mat = [[int(c) for c in row] for row in matrix]
    # 构建前缀和数组
    prefix = [[0]*(cols+1) for _ in range(rows+1)]
    for i in range(rows):
        row_sum = 0
        for j in range(cols):
            row_sum += mat[i][j]
            prefix[i+1][j+1] = prefix[i][j+1] + row_sum
    
    max_side = 0
    # 倒序尝试最大可能的边长
    for side in range(min(rows, cols), 0, -1):
        # 遍历所有可能的左上角位置
        for i in range(rows - side + 1):
            for j in range(cols - side + 1):
                # 计算子矩阵的和
                total = prefix[i+side][j+side] - prefix[i][j+side] - prefix[i+side][j] + prefix[i][j]
                if total == side * side:
                    return side * side
    return max_side

4. 优化索引存储与处理 #

避免反复将索引转换为列表，改用布尔矩阵标记有效位置。例如，对于尺寸n的有效位置，尺寸n+1的有效位置必须是尺寸n有效位置的子集，且其右、下、右下三个方向的位置也属于尺寸n的有效位置，这样可以直接基于布尔矩阵进行更新，无需重新计算卷积。

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