在大矩阵内移动正方形，找出重叠的最小数目

Question

我有一个方阵和一个较小的方阵，它在矩阵内所有可能的位置移动(不出矩阵)。我需要在所有可能的重叠中找到最小的数。

问题是两者的大小都可以达到数千。有什么快速的方法吗?

我知道一种方法-如果有一个数组而不是矩阵，一个窗口而不是正方形，我们可以在线性时间内使用deque。

提前感谢。

编辑:

例子矩阵:

1 3 6 2 5
8 2 3 4 5
3 8 6 1 5
7 4 8 2 1
8 0 9 0 5

对于大小为3的正方形，总共可能有9个重叠。对于每个重叠，矩阵形式的最小数为:

1 1 1
2 1 1
0 0 0

Answer 1

这是可能的O(k * n^2)与您的deque的想法:

如果您的小方块是k x k，迭代矩阵中从1到k的第一行元素，并通过预先计算矩阵每列中从1到k，从2到k + 1等元素的最小值(此预计算将采用O(k * n^2)))将其视为数组。这是你的第一行:

*********
1 3 6 2 5
8 2 3 4 5
3 8 6 1 5
*********
7 4 8 2 1
8 0 9 0 5

我提到的预计算将为您提供每列的最小值，因此您将把问题简化为1d数组问题。

然后继续从2到k + 1的元素行:

1 3 6 2 5
*********
8 2 3 4 5
3 8 6 1 5
7 4 8 2 1
*********
8 0 9 0 5

将有O(n)行，您将能够在O(n)中解决每一行，因为我们的预计算允许我们将它们减少到基本数组。