Leetcode -218- Skyline issues
[Blog link]
The path to learning at 🐔
The nuggets home page
[B].
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] indicates that lefti is the X coordinate of the left edge of the ith building. Righti is the X coordinate of the right edge of building I. Heighti is the height of the ith building. 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 building on the far right, and the y-coordinate is always zero0, 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. Such as [[...2 3], [4 5], [7 5], [11 5], [12 7]... ] Is not correct answer case; The three heights are5The lines should be merged into one in the final output: [...[2 3], [4 5], [12 7],... ] The sample1: 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[] 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. The sample2: input: buildings = [[0.2.3], [2.5.3] output: [[0.3], [5.0]] tip:1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1Buildings by Lefti non-decreasing order Related Topics Tree array Line segment tree array divide and conquer ordered set scan line heap (priority queue) 👍430 👎 0
Copy the code[答 案]
Leetcode topic link
[making address]
Code link
[introduction]
Idea 1: Violent scanning
- Output point coordinate requirements
- The next point is different in height from the current node, and a single inflection point line can be determined through the two nodes
- Boundary case: the first node is the abscissa of the first point and its height, and the abscissa of the last point is the abscissa of the last node and 0
- And it turns out that what we’re looking for is the highest height of each interval
- The list output is then made by this maximum height change
- Use Map to store the maximum height of each node
- Map seems to have no more use than list as a maximum integer segment
- Direct memory overflow
public List<List<Integer>> getSkyline(int[][] buildings) {
List<List<Integer>> res = new ArrayList<>();
// Initial node
List<Integer> xh = new ArrayList<>();
for (int i = 0; i < buildings[0] [0]; i++) {
xh.add(0);
}
for (int[] nums : buildings
) {
int l = nums[0], r = nums[1], h = nums[2];
while (l < r) {
// This part of TODO can be optimized
while (xh.size() < l) {
xh.add(0);
}
if(xh.size() == l) { xh.add(h); } xh.set(l, Math.max(xh.get(l), h)); l++; }}int index = 0;
// Establish the initial node
for (; index < xh.size(); index++) {
if(xh.get(index) ! =0) {
List<Integer> start = new ArrayList<>();
start.add(index);
start.add(xh.get(index));
res.add(start);
break; }}int temp = xh.get(index);
while (index < xh.size() - 1) {
if(xh.get(index) ! = temp) { List<Integer> node =new ArrayList<>();
node.add(index);
node.add(xh.get(index));
res.add(node);
temp = xh.get(index);
}
index++;
}
List<Integer> end = new ArrayList<>();
end.add(xh.size());
end.add(0);
res.add(end);
return res;
}
Copy the code
Idea 2: Scan lines
- Try to record intervals using a map
- Failed because the map changes when the interval is updated
- Read the three leaf big guy’s problem solution or do not understand the origin of the idea of pretreatment
- But I get the idea
- Let me put it in a more general way as I understand it
- First of all, we need to understand what exactly the printed point is: according to the scan line observation, it can be found that the printed point is the left end of the rectangle formed by every two scan lines that meet the conditions
- Secondly, we need to understand that there is a special case, that is, the right extension line of the previous rectangle may be the same as the current rectangle extension line, that is, the left end of the current rectangle should be moved forward to the previous left end
- Record the left and right endpoints of each rectangle for easy identification
- We can label height with positive and negative values
- So when height is negative on the left, height is positive on the right
- A large root heap ensures that each top left endpoint is output in turn
public List<List<Integer>> getSkyline(int[][] buildings) {
List<List<Integer>> res = new ArrayList<>();
// Record the left and right endpoints of each rectangle. In order to distinguish the left and right endpoints, we can mark the positive and negative values of height
Height is negative for the left endpoint, and height is positive for the right endpoint
List<int[]> ps = new ArrayList<>();
for (int[] b : buildings) {
int l = b[0], r = b[1], h = b[2];
ps.add(new int[]{l, -h});
ps.add(new int[]{r, h});
}
// The standard for sorting is to sort by the x-coordinate, determine the points on each x-coordinate, and then select
Collections.sort(ps, new Comparator<int[] > () {@Override
public int compare(int[] a, int[] b) {
// sort by abscissa
if (a[0] != b[0]) {
return a[0] - b[0];
}
// Sort by height
return a[1] - b[1]; }});// large root heap (guaranteed)
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); res.add(list); prev = cur; }}return res;
}
Copy the code