PHP | LeetCode

Задача: 218. The Skyline Problem
Сложность: hard

Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности.
Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:
lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

👨‍💻

Алгоритм:

1⃣Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2⃣Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

3⃣Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат.

😎

Решение:

class Solution {
    public function getSkyline($buildings) {
        $edgeSet = [];
        foreach ($buildings as $building) {
            $left = $building[0];
            $right = $building[1];
            $edgeSet[$left] = true;
            $edgeSet[$right] = true;
        }
        $edges = array_keys($edgeSet);
        sort($edges);

        $edgeIndexMap = [];
        foreach ($edges as $index => $edge) {
            $edgeIndexMap[$edge] = $index;
        }

        $heights = array_fill(0, count($edges), 0);

        foreach ($buildings as $building) {
            $left = $building[0];
            $right = $building[1];
            $height = $building[2];
            $leftIndex = $edgeIndexMap[$left];
            $rightIndex = $edgeIndexMap[$right];

            for ($idx = $leftIndex; $idx < $rightIndex; ++$idx) {
                $heights[$idx] = max($heights[$idx], $height);
            }
        }

        $answer = [];

        foreach ($heights as $i => $currHeight) {
            $currPos = $edges[$i];

            if (empty($answer) || end($answer)[1] != $currHeight) {
                $answer[] = [$currPos, $currHeight];
            }
        }
        return $answer;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post