Наибольший размер прямоугольника после каждого запроса (алгоритм)

Question

Я недавно сталкивался с этим алгоритмическим c вопросом в интервью. Вопрос звучит примерно так:

Первоначально задан прямоугольник (начиная с начала координат (0,0) и заканчивая (n, m)). Тогда есть q запросов, таких как x = r или y = c, которые в основном делят начальные прямоугольники на меньшие прямоугольники. После каждого запроса мы должны возвращать самый большой размер прямоугольника, который в настоящее время существует.

См. Диаграмму:

Итак, здесь мы изначально получили прямоугольник от (0,0) до (6,6) [квадрат на самом деле !!]. Теперь после 1-го запроса (показано пунктирной линией выше) x = 2, самый большой размер прямоугольника равен 24. После второго запроса y = 1, самый большой размер прямоугольника равен 20. И это так и продолжается.

Мой подход к решению этой проблемы:

При каждом запросе найдите:

1. The largest interval on the x axis (maxX) [keep storing all the x = r values in a list]

2. The largest interval on y axis (maxY) [keep storing all the y = c values in another list]

На каждый запрос ваш ответ будет (maxX * maxY)

Для поиска 1 и 2 у меня будет перебирать весь список, что не очень эффективно.

Итак, у меня есть 2 вопроса:

Правильно ли мое решение? Если нет, то каков правильный подход к проблеме. Если да, как я могу оптимизировать свое решение?

Answer 1

Это правильно, но занимает O (n) времени на запрос.

Для каждого измерения вы можете иметь одно двоичное дерево поиска (или другой отсортированный контейнер с операциями O (log n)) для координаты (изначально две) и одна для интервала размеры . Затем для каждого запроса в этом измерении:

1. Добавьте новую координату к координатам.
2. Из ее соседей вычислите старый размер интервала и удалите его из размеров.
3. Вычислить размеры двух новых интервалов и добавить их к размерам.
4. Самый большой размер находится в конце размеров.

Будет O (log n) за запрос.

Answer 2

Да, ваш алгоритм верен.

Чтобы оптимизировать его, прежде всего, рассмотрите только одно измерение, потому что два измерения в вашей геометрии полностью ортогональны.

Итак, вам нужно иметь структуру данных, которая содержит разбиение интервала на подинтервалы и поддерживает быстрое применение этих двух операций:

1. Разделить данный интервал на две
2. Найти наибольшее интервал

Это можно сделать с помощью двух отсортированных списков, один из которых отсортирован по координатам, а другой - по размеру. У вас должны быть указатели из одной структуры данных в другую, и наоборот.

Для реализации операции «разбиения»:

1. Найдите интервал, который вы должны разделить, используя двоичный файл поиск в отсортированном по координатам списке
2. Удалить интервал из обоих списков
3. Добавить два меньших интервала в оба списка