我有一个正方形矩阵和一个较小的正方形，它在矩阵内所有可能的位置移动(不超出矩阵)。我需要在所有这些可能的重叠中找到最小的数字。
问题是两者的大小都可以达到数千。有什么快速的方法吗？
我知道一种方法 - 如果有一个数组而不是矩阵和一个窗口而不是正方形，我们可以使用 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) 中是可能的:
如果您的小方 block 是 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
我提到的预计算将为您提供每一列中的最小值，因此您可以将问题简化为一维数组问题。
然后继续从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) 中解决每一行，因为我们的预计算允许我们将它们简化为基本数组.
关于algorithm - 在大矩阵内移动正方形，找到重叠的最小数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15968587/