This article is participating in Python Theme Month. See the link for details
Topic describes
This is the 218. Skyline problem on LeetCode. Difficulty is difficult.
Tag: “Scanline problem”, “priority queue”
The skyline of a city is the outer outline of all the buildings in the city as viewed from a distance. To give you the location and height of all the buildings, return to the skyline formed by these buildings.
The geometric information of each building is represented by the array buildings, where the triad buildings[I] = [lefti, righti, Heighti] is represented by:
left[i]Is the x coordinate of the left edge of building I.right[i]Is the x coordinate of the right edge of building I.height[i]Is the height of building I.
The skyline should be represented as a list of “key points” in the format [[X1,y1],[x2,y2],… And sort them by the x coordinate. The key point is the left end of the horizontal segment. The last point in the list is the end of the right-most building, and the y-coordinate is always 0, used only to mark the end of the skyline. In addition, the ground between any two adjacent buildings should be considered part of the skyline profile.
Note: the output skyline must not have consecutive horizontal lines of the same height. For example, […[2 3], [4 5], [7 5], [11 5], [12 7]… Is the wrong answer; Three height is 5 lines should be in the final output into a: [… [2, 3], [4, 5], [7],…
Example 1:
Input: buildings = [,9,10 [2], [3,7,15], [5,12,12], [15, 10], [19,24,8]] output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] explanation: figure A shows the positions and heights of all the buildings entered, and figure B shows the skyline formed by these buildings. The red dots in Figure B represent key points in the output list.Copy the codeExample 2:
Buildings = [[0,2,3],[2,5,3]]Copy the codeTip:
- 1 <= buildings.length <=
- 0 <= lefti < righti <=
– 1 - 1 <= heighti <=
– 1 - Buildings is in lefti non-descending order
Fundamental analysis
This is a special scan line problem 🤣🤣🤣
Not the perimeter, not the area, but the left end of all the horizontal lines in the contour 🤣🤣🤣
So this is not a scanline problem that has to be solved with a “line tree” (because there is no interval query problem to worry about).
The core of the scan line is to divide irregular shapes into regular rectangles, either horizontally or vertically.
Scan line
In this case, the corresponding scanline segmentation shape is shown as follows:
It is not difficult to see that a rectangle can be defined by two adjacent horizontal coordinates and the maximum height.
They want us to print the left end of the “top” of each rectangle and skip the edges that extend from the “top” of the previous rectangle.
Therefore we need to maintain a maximum height in real time, which can be used with priority queues (heaps).
Implementation, we can all around in the first recorded buildingsbuildingsbuildings abscissa endpoint and height, and according to the smallest abscissa endpoint.
In the process of traversing from front to back (traversing each rectangle), discuss the situation according to the points traversed currently:
-
Left end: Because it is the left end, there must be an edge that extends from the right, but it is not necessarily the edge that needs to be recorded, since we only need to record the topmost edge in the same rectangle. At this time can be the height of the team;
-
Right endpoint: this means that a previous line extending to the right has ended and the height of the line should be removed from the queue (the line representing this end is not considered).
We then extract the current maximum height from the priority queue. To prevent the current line from overlapping with the line stretched “above” the previous rectangle, we need to use a variable prev to record the height of the previous record.
Java code:
class Solution {
public List<List<Integer>> getSkyline(int[][] bs) {
List<List<Integer>> ans = new ArrayList<>();
// Preprocess all the points, for sorting convenience, for the left endpoint, make the height negative; Let's make the height positive for the right endpoint
List<int[]> ps = new ArrayList<>();
for (int[] b : bs) {
int l = b[0], r = b[1], h = b[2];
ps.add(new int[]{l, -h});
ps.add(new int[]{r, h});
}
// Sort by x-coordinate first
// If the x-coordinate is the same, sort by the left endpoint
// If the left/right endpoints are the same, sort by height
Collections.sort(ps, (a, b)->{
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
});
/ / big root pile
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
int prev = 0;
q.add(prev);
for (int[] p : ps) {
int point = p[0], height = p[1];
if (height < 0) {
// If it is a left endpoint, there is a recordable edge extending to the right, and the height is put into the priority queue
q.add(-height);
} else {
// If it is the right endpoint, the edge is finished and the current height is removed from the queue
q.remove(height);
}
// Retrieves the highest height, which can be recorded if it does not currently coincide with the edges extending "above" the previous rectangle
int cur = q.peek();
if(cur ! = prev) { List<Integer> list =newArrayList<>(); list.add(point); list.add(cur); ans.add(list); prev = cur; }}returnans; }}Copy the codePython 3 code:
from sortedcontainers import SortedList
class Solution:
def getSkyline(self, buildings: List[List[int]]) - >List[List[int]] :
ans = []
# Preprocess all points, for sorting convenience, for left endpoints, make height negative; Let's make the height positive for the right endpoint
ps = []
for l, r, h in buildings:
ps.append((l, - h))
ps.append((r, h))
Sort by x first
If the x-coordinate is the same, sort by the left endpoint
Sort by height if the left/right endpoints are the same
ps.sort()
prev = 0
An ordered list acts as a large root heap
q = SortedList([prev])
for point, height in ps:
if height < 0:
If it is a left endpoint, there is a recordable edge extending to the right, and the height is placed in the priority queue
q.add(-height)
else:
# If it is the right endpoint, the edge is finished, and the current height is removed from the queue
q.remove(height)
The highest height can be recorded if it does not currently coincide with the edges extending "above" the previous rectangle
cur = q[-1]
ifcur ! = prev: ans.append([point, cur]) prev = curreturn ans
Copy the code- Time complexity: the number of matrices to be processed versus
Proportional to each matrix required to maintain the height of the priority queueremoveOperation costs up front
Complexity to find, and then pass
Complexity is removed
. The overall complexity is
- Space complexity: O(n)O(n)O(n)
Answering questions
1. What does it mean to store the height of the left endpoint as a negative number and then sort it?
Here is just for convenience, so take this approach, of course, can also use more than one to refer to the “left and right”.
As long as the result can achieve the following sorting rules:
- First, sort from smallest to largest strictly on the x-coordinate
- For a certain x-coordinate, multiple points may appear at the same time and should be handled according to the following rules:
- Process the left endpoint first, then the right endpoint
- If they are both left endpoints, they are processed “from large to small” by height (adding height to priority queue)
- If they are both right endpoints, they are processed “from smallest to largest” by height (removing height from priority queue)
Code:
class Solution {
public List<List<Integer>> getSkyline(int[][] bs) {
List<List<Integer>> ans = new ArrayList<>();
List<int[]> ps = new ArrayList<>();
for (int[] b : bs) {
int l = b[0], r = b[1], h = b[2];
ps.add(new int[]{l, h, -1});
ps.add(new int[]{r, h, 1});
}
* For a certain x-coordinate, there may be multiple points at the same time, should be handled according to the following rules: * 1. The left endpoint is processed first, then the right endpoint * 2. If both are left endpoints, processing is done "from largest to smallest" by height (adding height to priority queue) * 3. If they are both right endpoints, they are processed "from the smallest to the largest" in height (the height is removed from the priority queue) */
Collections.sort(ps, (a, b)->{
if (a[0] != b[0]) return a[0] - b[0];
if (a[2] != b[2]) return a[2] - b[2];
if (a[2] = = -1) {
return b[1] - a[1];
} else {
return a[1] - b[1]; }}); PriorityQueue<Integer> q =new PriorityQueue<>((a,b)->b-a);
int prev = 0;
q.add(prev);
for (int[] p : ps) {
int point = p[0], height = p[1], flag = p[2];
if (flag == -1) {
q.add(height);
} else {
q.remove(height);
}
int cur = q.peek();
if(cur ! = prev) { List<Integer> list =newArrayList<>(); list.add(point); list.add(cur); ans.add(list); prev = cur; }}returnans; }}Copy the code2. Why do I add a priority queue before processing it
？
Since the problem itself requires us to take the “lower right” point of a complete contour, we need to add 000 first.
Those are the points circled below:
3. Priority queueremoveOperation becomes the bottleneck, how to optimize?
The remove operation of the priority queue must be searched by the complexity of O(n)O(n)O(n) O, and then deleted by the complexity of O(logn)O(\log{n})O(logn). Therefore, the complexity of the entire remove operation is O(n)O(n)O(n) O(n), resulting in the overall complexity of our algorithm is O(n2)O(n^2)O(n2).
Optimization methods include: using TreeMap based on red black tree to replace priority queue; Or use “hash table” to record “the height of the deleted operation” and “the number of deleted operations”. Check whether the heap top height has been marked for deletion before each use. If so, poll operation is conducted and the number of deleted operations is updated until a heap top height that has not been deleted is found.
Code:
class Solution {
public List<List<Integer>> getSkyline(int[][] bs) {
List<List<Integer>> ans = new ArrayList<>();
List<int[]> ps = new ArrayList<>();
for (int[] b : bs) {
int l = b[0], r = b[1], h = b[2];
ps.add(new int[]{l, h, -1});
ps.add(new int[]{r, h, 1});
}
* For a certain x-coordinate, there may be multiple points at the same time, should be handled according to the following rules: * 1. The left endpoint is processed first, then the right endpoint * 2. If both are left endpoints, processing is done "from largest to smallest" by height (adding height to priority queue) * 3. If they are both right endpoints, they are processed "from the smallest to the largest" in height (the height is removed from the priority queue) */
Collections.sort(ps, (a, b)->{
if (a[0] != b[0]) return a[0] - b[0];
if (a[2] != b[2]) return a[2] - b[2];
if (a[2] = = -1) {
return b[1] - a[1];
} else {
return a[1] - b[1]; }});// Record the height of the deletion operation and the number of deletions
Map<Integer, Integer> map = new HashMap<>();
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
int prev = 0;
q.add(prev);
for (int[] p : ps) {
int point = p[0], height = p[1], flag = p[2];
if (flag == -1) {
q.add(height);
} else {
map.put(height, map.getOrDefault(height, 0) + 1);
}
while(! q.isEmpty()) {int peek = q.peek();
if (map.containsKey(peek)) {
if (map.get(peek) == 1) map.remove(peek);
else map.put(peek, map.get(peek) - 1);
q.poll();
} else {
break; }}int cur = q.peek();
if(cur ! = prev) { List<Integer> list =newArrayList<>(); list.add(point); list.add(cur); ans.add(list); prev = cur; }}returnans; }}Copy the code- O(nlogn)O(n\log{n})O(nlogn)
- Space complexity: O(n)O(n)O(n)
The last
This is No.218 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 topics in LeetCode, some of which have locks, we will first finish all the topics without locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.