Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).
📋 Описание задачи
Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.
💡 Идея
Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.
🛠️ Детали подхода
-
Представление и сортировка:
- Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
- Сортируем ячейки по высоте в порядке возрастания.
-
Структура объединения множеств:
- Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.
Читать дальше →