kniost

谁怕，一蓑烟雨任平生

0%

LeetCode 218. The Skyline Problem 空中轮廓线问题

发表于 更新于 分类于
本文字数： 4.5k 阅读时长 ≈ 4 分钟
经典的空中轮廓线问题的扫描线解法

题目原文

218. The Skyline Problem

Difficulty: Hard

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points“ (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

解法

这是一个经典的扫描线问题，给了一堆建筑，并需要找出轮廓，轮廓的定义就是重叠的建筑物中远远看去最大高度发生变化的点，这里称之为轮廓点。

根据扫描线问题的基本思路，我们将一个建筑物拆解成两条线，一条上升，一条下降，这样，每条线具有三个特征，即坐标，高度和上升状态，我们要去找到最大高度发生变化的点，就需要对这些线进行排序访问。

如何知道当前的最大高度

显然，在动态添加线时，使用最大堆（PriorityQueue)或者红黑树Set（TreeSet）可以轻易求出当前的最大高度，但是在删除一个建筑时，TreeSet的表现是最好的O(log(n))，所以我们选用TreeSet用于存储目前存在的建筑，并使用first()(按高度从大到小)方法获取最高的高度。

对线以什么顺序排序

经过分析，我们可以按照以下优先级对访问顺序进行排序：

  1. 先比较坐标，坐标不同时，按照自然顺序，坐标小的优先
  2. 坐标相同时，比较上升和下降状态，上升优先
  3. 坐标和状态均相同时，如果是上升状态，则高度更高的优先；下降状态时，高度更低的优先

下面是对这个优先级的解释：

  1. 先按照坐标比较这一点毋庸置疑，扫描线问题都是这样做的。
  2. 坐标相同时，如果不管状态，直接比较高度，就可能出现高低交替的情况，导致同一个坐标出现数个轮廓点。所以需要先按照状态排序，问题是上升优先还是下降优先呢？考虑一种情况，就是两个相同高度的建筑连接在一起，按照题意，这种情况下中间其实是没有发生高度变化的。如果先下降，后上升，那么最大高度就发生了两次变化，这明显是不对的。所以应该先上升，后下降。
  3. 如果坐标和状态状态相同的话呢？显然，对于上升状态，我们应该先扫更高的，这样那些矮的同坐标的上升线无法改变最大高度，便不会记录最高点。对于下降状态，我们要删除建筑，所以应该先把低的删除，避免引起高度的变化。比如有两个坐标重叠的建筑，高度不同，那么在扫描到下降线时必须要先下降高度小的，否则高度会发生两次变化。

如何控制建筑的进出

还有一个问题就在于我们如何控制一个建筑的进出，目前使用了线的一个成员变量记录下降线对应的上升线。

还有什么问题？

在定义TreeSet的Comparator的时候需要注意，TreeSet在插入元素时是根据Comparator判断元素是否相等的，这样如果Comparator的compare()方法中只根据高度来判断时，同一高度的建筑物将只能存储一个！所以有必要再加入一个参数用于区分这些建筑，可以直接使用hashCode()或者新增一个参数。

下面是个人的代码，仅供参考，使用了opposite成员变量记录下降线对应的上升线。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    public static final int UP = 1, DOWN = -1;
    class Line {
        public int x, height, status;
        public Line opposite;
        public Line(int x, int height, int status, Line opposite) {
            this.x = x;
            this.height = height;
            this.status = status;
            this.opposite = opposite;
        }
    }
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        if (buildings == null || buildings.length == 0) {
            return result;
        }
        // 将建筑拆成两条线，并记录下降线对应的上升线
        Line[] lines = new Line[buildings.length * 2];
        for (int i = 0; i < buildings.length; i++) {
            int[] b = buildings[i];
            int j = i * 2;
            lines[j] = new Line(b[0], b[2], UP, null);
            lines[j + 1] = new Line(b[1], b[2], DOWN, lines[j]);
        }
        // 按照三个优先级排序
        Arrays.sort(lines, new Comparator<Line>() {
            @Override
            public int compare(Line l1, Line l2) {
                if (l1.x != l2.x) {
                    return l1.x - l2.x;
                }
                if (l1.status != l2.status) {
                    return l2.status - l1.status;
                }
                if (l1.status == UP) {
                    return l2.height - l1.height;
                } else {
                    return l1.height - l2.height;
                }
            }
        });
        // 使用lambda表达式定义TreeSet的Comparator，此处的heap只是形象表达，内部数据结构其实是红黑树
        TreeSet<Line> heightHeap = new TreeSet<>((a, b) -> b.height == a.height ? a.hashCode() - b.hashCode() : b.height - a.height);
        int curMax = 0;
        for (Line tmp : lines) {
            // 上升时将建筑加入
            if (tmp.status == UP ) {
                heightHeap.add(tmp);
                if (tmp.height > curMax) {
                    result.add(new int[] {tmp.x, tmp.height});
                    curMax = tmp.height;
                }
            // 下降时将建筑删除
            } else {
                heightHeap.remove(tmp.opposite);
                // 特殊情况：删除以后没有建筑
                if (heightHeap.size() == 0) {
                    curMax = 0;
                    result.add(new int[] {tmp.x, 0});
                } else if (heightHeap.first().height < curMax) {
                    curMax = heightHeap.first().height;
                    result.add(new int[] {tmp.x, curMax});
                }
            }
        }
        return result;
    }
}