К задачам

Подматрица с максимальным размахом

СложнаяАлгоритмы
Лучше работает на десктопе
МатрицаСкользящее окноМонотонная очередь

Дана матрица целых чисел и размеры окна height x width.

Нужно найти левый верхний угол подматрицы фиксированного размера, где размах значений максимален:

range = max(window) - min(window)

Если оптимальных окон несколько, верните самое раннее по обходу сверху вниз, слева направо.

Сигнатура

def max_range_submatrix(matrix: list[list[int]], height: int, width: int) -> list[int]:

Верните [row, col] — индекс верхнего левого угла.

Примеры

Пример 1

Вход:
matrix = [[1,2,3],[4,100,6],[7,8,9]]
height = 2
width = 2
Выход:[0,0]

Окно с большим выбросом

Пример 2

Вход:
matrix = [[5,5,5],[5,5,5]]
height = 1
width = 2
Выход:[0,0]

Все окна равны

Пример 3

Вход:
matrix = [[1,9,2,8],[3,4,5,6],[7,0,1,2]]
height = 2
width = 3
Выход:[0,0]
Код
Python · Ctrl/⌘ + Enter для запуска
Лимит
08:00
Консоль
Нажмите кнопку запуска или Ctrl+Enter
Подматрица с максимальным размахом — Алгоритмы задача — ML Mentor