LeetCode 218: The Skyline Problem
Problem Description
Explanation:
The problem can be solved using a data structure like a priority queue (max heap) to keep track of the heights of the buildings. We iterate through the buildings and for each building, we add the left corner with a negative height to indicate the start of a building, and the right corner with a positive height to indicate the end of a building. By doing this, we can keep track of the heights and their respective positions.
We iterate through the buildings in sorted order of their left corners. At each iteration, we update the current maximum height and compare it with the previous maximum height to determine if there is a transition in the skyline. If there is a transition, we record the key point in the skyline.
Time complexity: O(n log n) where n is the number of buildings Space complexity: O(n) for the priority queue
:
Solutions
import java.util.*;
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<List<Integer>> result = new ArrayList<>();
List<int[]> buildingPoints = new ArrayList<>();
for (int[] building : buildings) {
buildingPoints.add(new int[]{building[0], -building[2]});
buildingPoints.add(new int[]{building[1], building[2]});
}
Collections.sort(buildingPoints, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else {
return a[1] - b[1];
}
});
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(0);
int prevMaxHeight = 0;
for (int[] point : buildingPoints) {
if (point[1] < 0) {
maxHeap.offer(-point[1]);
} else {
maxHeap.remove(point[1]);
}
int currentMaxHeight = maxHeap.peek();
if (prevMaxHeight != currentMaxHeight) {
List<Integer> keyPoint = new ArrayList<>();
keyPoint.add(point[0]);
keyPoint.add(currentMaxHeight);
result.add(keyPoint);
prevMaxHeight = currentMaxHeight;
}
}
return result;
}
}Related LeetCode Problems
Loading editor...