Переместить квадрат внутри большой матрицы, найти минимальное число в перекрытии

Question

У меня есть матрица sqaure и меньший квадрат, который перемещается внутри матрицы во всех возможных положениях (не выходит из матрицы). Мне нужно найти наименьшее число во всех таких возможных перекрытиях.

Проблема в том, что размеры обоих могут достигать тысяч. Любой быстрый способ сделать это?

Я знаю один способ - если есть массив вместо матрицы и окно вместо квадрата, мы можем сделать это в линейной времени с использованием 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), потому что наше предвычисление позволяет свести их к основным массивам ,