Сложность: 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 {
func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
var edgeSet = Set<Int>()
for building in buildings {
edgeSet.insert(building[0])
edgeSet.insert(building[1])
}
let edges = Array(edgeSet).sorted()
var edgeIndexMap = [Int: Int]()
for i in 0..<edges.count {
edgeIndexMap[edges[i]] = i
}
var heights = [Int](repeating: 0, count: edges.count)
for building in buildings {
let left = building[0], right = building[1], height = building[2]
let leftIndex = edgeIndexMap[left]!, rightIndex = edgeIndexMap[right]!
for idx in leftIndex..<rightIndex {
heights[idx] = max(heights[idx], height)
}
}
var answer = [[Int]]()
for i in 0..<heights.count {
let currHeight = heights[i], currPos = edges[i]
if answer.isEmpty || answer.last![1] != currHeight {
answer.append([currPos, currHeight])
}
}
return answer
}
}Ставь 👍 и забирай 📚 Базу знаний