分治算法--天际线问题

分治算法--天际线问题

十月 10, 2019

分治算法–天际线问题

题目描述：

每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标，Hi
是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li >
0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。

例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24
8] ] 。

输出是以 [ [x1,y1], [x2, y2], [x3, y3], … ]
格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8],
[24, 0] ]。

说明:

任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。 输入列表已经按左 x 坐标 Li 进行升序排列。 输出列表必须按 x
位排序。 输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12
7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-skyline-problem
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法思路：
官方给的分支算法的解法，看了半天，自己也写了一遍，什么没懂，归并地方一直出错，索性自己写得了。（还事先重新写了一遍归并排序，抄官方的代码抄到我怀疑我数据结构白学了。）
我的做法：第一步大致都一样，就是分治，具体代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
    len_buildings = len(buildings)

    if len_buildings == 0:
        return []
    if len_buildings == 1:
        building_start, building_end, building_height = buildings[0]
        return [[building_start, building_height], [building_end, 0]]

    left_skyline = self.getSkyline(buildings[:len_buildings // 2])
    right_skyline = self.getSkyline(buildings[len_buildings // 2:])

    result = self.merge_building(left_skyline, right_skyline)
    return result

归并的思想就是将N个大楼分成两部分，分别对左右两部分求解，大问题化小问题，最后如果左边部分没有建筑物，返回空List对象[]，如果只有一栋建筑，返回这栋建筑的天际线（这个就简单了），比如题目中的个大楼[2, 9, 10]指的就是x坐标2到9，高度为10的大楼，那么它的天际线就是[[2, 10][9, 0]]（只需记录高度变化的那个点）

这样就获得了以上的递归函数，之后的问题就是如果合并俩个天际线left_skyline和right_skyline。下面几个解答我都没看懂，所以就自己想了一个，前两种想法最后都失败了，都是按照别人的解答“临摹”的算法，所以最后浏览器一关，自己想吧。

我想的是，假设有两个无限长的直线（我称之为current_l和current_r），分别记录左边部分天际线和右边部分的上次访问时的高度，一开始都设定为0，然后开始遍历图（List）中的点。

如果遍历到左边部分的点，会出现两种情况，这个点对我们的天际线产生了影响，或者没有任何影响。以下以遍历到左边部分的点left_dot作说明：

1
2
3
---------- current_r ----------
---------- left_dot ----------
---------- current_l ----------

以上我把点也延伸成一条直线，那么如果我想要对当前的天际线产生影响，那我必须对于上一次的高度current_l产生变化，比current_l高的话，那说明这个点升高了，那么怎么判断我这个点有没有把整个天际线“撑”高呢？

那就要看left_dot对于current_r的位置了，也就是说，我之前访问过的右边部分的高度如果还没我现在这个点高的话，那么天际线必然被撑高了，即上面的情况，在这种情况下，我的目前访问到的这个点产生的高度变化被current_r覆盖了。

所以产生变化的情况一如下：

1
2
3
---------- left_dot ----------
---------- current_r ----------
---------- current_l ----------

那么点下降的情况呢？
我实验得到的结果是，只有当left_dot比current_l低，且不能比current_r还要低（即left_dot >= current_r）时，left_dot的下降变化才会对天际线产生影响。因为，如果left_dot下降到比上次访问时两部分的高度还要低时，这个变化会被右边部分覆盖。

1
2
3
---------- current_l ----------
---------- left_dot ----------
---------- current_r ----------

此外还有一种下降的情况（这是在第二次提交时，解答出错时才看到的情况，一开始根本没考虑到），就是点在下降过程中被另一部分“拦截”了（这是left_dot比current_l和current_r都低时的特例，要求current_l > current_r > left_dot）

1
2
3
---------- current_l ----------
---------- current_r ----------
---------- left_dot ----------

简而言之，左边部分要影响天际线（即左边点要放入结果集中），左边部分要么升高到足以覆盖右边部分，要么下降到仍然可以覆盖右边部分的位置，亦或是，在下降的过程中被右边部分截住了（其实把两部分的交点看作一个新的点），因为两部分始终处于覆盖和被覆盖的关系中。

所以一开始我决定先进行一遍归并排序，这样可以获得点排序好的List，但是写完归并后再去处理合并好的result时，发现写法和归并是一样的，然后发现这两部分可以合并在一起，因为归并每次排序时都是从两个数组中选一个最小的点出来，那么这一步其实已经可以知道当前点来自左边还是右边，所以可以一边归并排序（实则并没有排序），一边绘制天际线（这也是解答中我看不懂的地方）
具体代码实现如下：

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
def merge_building(self, left: List[List], right: List[List]) -> List[List]:
    point_l = point_r = 0
    result = []
    current_l = current_r = 0

    while point_l < len(left) and point_r < len(right):
        left_x, left_h = left[point_l]
        right_x, right_h = right[point_r]

        if left_x < right_x:
            # 当前的点为左边大楼的点
            if (left_h > current_l and left_h > current_r) or (current_r <= left_h < current_l):
                result.append([left_x, left_h])
            # left下降的趋势被right挡住了
            elif left_h < current_r < current_l:
                result.append([left_x, current_r])
            current_l = left_h
            point_l += 1
        elif left_x > right_x:
            # 当前的点为右边大楼的点
            if (right_h > current_l and right_h > current_r) or (current_l <= right_h < current_r):
                result.append([right_x, right_h])
            elif right_h < current_l < current_r:
                result.append([right_x, current_l])
            current_r = right_h
            point_r += 1
        if left_x == right_x:
            left_dh = left_h - current_l
            right_dh = right_h - current_r

            if left_dh + right_dh != 0:
                if left_dh > right_dh:
                    result.append([left_x, left_h])
                else:
                    result.append([left_x, right_h])
            current_l = left_h
            current_r = right_h
            point_l += 1
            point_r += 1

    while point_l < len(left):
        result.append(left[point_l])
        point_l += 1

    while point_r < len(right):
        result.append(right[point_r])
        point_r += 1

    return result

其中部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
if left_x == right_x:
    left_dh = left_h - current_l
    right_dh = right_h - current_r

    if left_dh + right_dh != 0:
        if left_dh > right_dh:
            result.append([left_x, left_h])
        else:
            result.append([left_x, right_h])
    current_l = left_h
    current_r = right_h
    point_l += 1
    point_r += 1

是考虑两栋大楼边界靠在一起的情况，这也是提交时官方的测试用例里我没考虑到情况，例如：

buildings_3 = [
    [1, 2, 1],
    [1, 2, 2],
    [1, 2, 3]
]

我想了一下这里要考虑四条边（上次高度两条边，当前点的两条边）的高低情况，所以想了很久怎么减少一些情况（减少if语句），我的做法是计算当前两个点的高度相对变化率，如果变化率大（下降的情况对应负变化率），那么这个变化率对高度会产生影响。其实变化率很好算，因为我们记录了上一次的高度current_l和crrent_r，所以只需要用当前点的高度减去上一次的高度就是变化率了。

最后写了一天终于通过了，呵。

  1. 1. 分治算法–天际线问题