算法 - 在 nn 二维矩阵中找到 kk 集合的所有最大值

Question

我有一个 N*N 2D 矩阵。我想找到每组 k*k 子网格的所有最大值。什么应该是有效的 algorithm.For 示例，

N = 4, k = 2

0 1 3 1
5 2 1 4
2 3 0 7

输出：3, 4, 5

3 个来自

1 3
2 1

4 个来自

3 1
1 4

5 个来自

5 2
2 3

一些子集没有被计算在内，因为它们有未设置的位，0 在 k*k 限制内。例如，

1 4
0 7

Answer 1

如果你能保证没有一个元素是负数，那么你的问题确实可以在O(N²)次。诀窍是使用 sliding window minimum/maximum algorithm.

首先，运行输入矩阵每一行的滑动window最小值和最大值算法，给你两个N×(N − k + 1) 矩阵。例如：

Minimum matrix:
  0 1 1
  2 1 1
  2 0 0

Maximum matrix:
  1 3 3
  5 2 4
  3 3 7

接下来，运行滑动 window 两个各自矩阵的每一列上的最小值和最大值算法，给你两个 (N − k + 1)² 矩阵.

Minimum matrix:
  0 1 1
  2 0 0

Maximum matrix:
  5 3 4
  5 3 7

现在同时扫描两个矩阵，如果最小矩阵元素不为0，则输出最大矩阵对应的元素。因此我们输出 3, 4, 5.

Algorithm - Finding all maxima of kk sets in nn 2D Matrix