Войти Регистрация
Алгоритмы

112. Свободная зона на складе Маркета

Сложная

Пол склада Яндекс Маркета разбит на ячейки 1 × 1 м. В grid[r][c] стоит 1, если ячейка свободна, и 0, если там стеллаж, колонна или паллет.

Под сезонную приёмку нужна одна прямоугольная зона со сторонами вдоль сетки, целиком из свободных ячеек. Верните её наибольшую площадь в м².

Все строки одной длины. Пустая таблица — площадь 0.

В работе: Где на складе развернуть временную зону приёмки перед распродажей.

Пример 1

Ввод
grid = [[1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [0, 1, 1, 1, 0]]
Вывод
9

Столбцы 1..3 в строках 1..3 — зона 3 × 3 = 9 м².

Пример 2

Ввод
grid = [[0, 0], [0, 0]]
Вывод
0

Свободных ячеек нет.

Ограничения

  • 0 ≤ строк, столбцов ≤ 2000
  • grid[r][c] — 0 или 1
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def largest_free_zone(grid):
Монотонный стекГистограммаМатрицацельO(n)

Источник: наша задача на данных Яндекса. Условие пересказано своими словами.