我有一个正方形矩阵和一个较小的正方形，它在矩阵内所有可能的位置移动（不会超出矩阵）。我需要在所有这些可能的重叠中找到最小的数字。
问题是两者的大小都可以达到数千。有什么快速的方法吗？
我知道一种方法 - 如果有一个数组而不是矩阵和一个窗口而不是正方形，我们可以使用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
O(k * n^2)你的双端队列想法是可能的：
如果您的小方块是k x k，则迭代矩阵中从 1 到 的第一行元素，并通过预先计算矩阵每一列中从 1 到、从 2 到等k元素的最小值将其视为一个数组（此预计算将占用. 这就是你的第一行：kk + 1O(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
我提到的预计算将为您提供每一列的最小值，因此您将问题简化为一维数组问题。
然后继续从 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)因为我们的预计算允许我们将它们减少为基本数组。