0218 - The Skyline Problem

Other

June 01, 2023

题干

问题描述

源代码

破题

这道题的关键是能观察到：关键点是顺着 $x$ 轴的方向，当剪影的高度发生变化时确定的。

这样，如果能确定每个 $x$ 坐标对应的建筑物的最大高度，就能求出关键点。

解①：分段树

最直接的一个思路是把建筑列表里的每栋建筑的高度在它所属区间上标识出，这样就可以查询每个 $x$ 坐标的最大高度。

分段树（Segment Tree）就适用于这种情况：考虑分段树的里的批量更新，既支持批量累加，又支持批量赋值，而批量赋值就适用于当前这种给定区间标记高度的任务。

需要注意：

由于建筑间区间重叠，因此批量赋值和查询时要取（建筑高度）的最大值，作为剪影的代表；
建筑的右边缘的高度是无效的，也就是对于左右端的坐标分别为 $l$ 和 $r$ 的建筑，它的高度有效范围为 $[l, r)$

Python 实现¹

分段树

使用DFS 型的分段树来节省一半的内存。

由于实际上我们只使用批量赋值的信息，而不需要原信息，因此直接省略了树本身，只保留更新的结构。

有一点， Python 的函数调用是真的消耗时间，在 Rust 里面你可以随意地使用函数包装，实际上调用的成本几乎都可以被优化掉，因此可以基于 API 的人体工程学考虑，用 Cursor 类别处理“分段”信息，但在 Python 上，这种频繁调用地包装函数会导致运行时间变为 3 倍，于是我们不使用包装，而是把参数就地直接展开。

class SegmentTree():
    """DFS Layout,
    left: i+1,
    right: 2+2l
    """

    def __init__(self, data_len: int):
        # Just ignore self.tree
        self.assigned = [0] * 2 * data_len
        self.root = [0, data_len - 1, 0]

    def assign(self, val: int, l: int, r: int) -> None:
        """Override the smaller value"""
        self._assign(val, l, r, *self.root)

    def _assign(self, val: int, l: int, r: int, tl: int, tr: int, i: int) -> None:
        if l > r:
            return

        if l == tl and r == tr:
            self.assigned[i] = max(self.assigned[i], val)
        else:
            mid = (tl + tr) // 2
            subl = mid - tl + 1

            self._assign(val, l, min(mid, r), tl, mid, i + 1)
            self._assign(val, max(mid + 1, l), r, mid + 1, tr, i + 2 * subl)

    def query(self, l: int, r: int) -> int:
        """query [l, r] -> (x, h)"""
        return self._query(l, r, *self.root)

    def _query(self, l: int, r: int, tl: int, tr: int, i: int) -> int:
        if l > r:
            return 0

        if l == tl and r == tr:
            return self.assigned[i]
        else:
            mid = (tl + tr) // 2
            subl = mid - tl + 1

            if self.assigned[i]:
                self.assigned[i + 1] = max(
                    self.assigned[i + 1],
                    self.assigned[i],
                )

                self.assigned[i + 2 * subl] = max(
                    self.assigned[i + 2 * subl],
                    self.assigned[i],
                )

                self.assigned[i] = 0

            lv = self._query(l, min(mid, r), tl, mid, i + 1)
            rv = self._query(max(mid + 1, l), r, mid + 1, tr, i + 2 * subl)

            return max(lv, rv)

数据离散化

在测试里有专门的 $x$ 坐标很大的建筑物，如果直接按照 $x$ 坐标建树，性能将是不可接受的，需要进行离散化处理。

我们可以取建筑两端的 $x$ 坐标，用它们的排名压缩坐标轴。需要注意一点，如果用向量和下标的方式储存坐标与排名的对应关系，需要跳过重复的元素，否会产生同一坐标不同排名的情况，从而妨碍正确结果的求出。

完整过程

from typing import *
from bisect import bisect_right


class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        return solve(buildings)


def solve(buildings: List[List[int]]) -> List[List[int]]:
    # 数据离散化 (Discretization)

    x_data = [buildings[0][0]]

    for (l, _, _) in buildings[1:]:
        if x_data[-1] != l:
            x_data.append(l)

    for (_, r, _) in buildings:
        i = bisect_right(x_data, r)
        # i != 0 for right x-axis
        if x_data[i-1] != r:
            x_data.insert(i, r)

    x_map = {x: i for i, x in enumerate(x_data)}

    # Build Segment Tree by Batch Update

    segtree = SegmentTree(len(x_data))

    for (l, r, h) in buildings:
        l = x_map[l]
        r = x_map[r]
		# [l, r)
        segtree.assign(h, l, r-1)

    # Sweep Line

    res = []

    for i, x in enumerate(x_data):
        h = segtree.query(i, i)

        if not res or res[-1][1] != h:
            res.append([x, h])

    return res

# 分段树定义如上

解②：树状数组

如果说前面对分段树的改动还比较小²，那么树状数组的思路里面对树状数组的改动就比较tricky了，因为普通的树状数组，以下简称 BIT（Binary Indexed Tree），用某个点的前缀和表示该点的高度，那么任何 $x$ 轴靠前坐标上的高度更新都会影响后面位置的高度的计算。

因此我们对树状数组的改动是让它前面位置的更新不影响后面位置前缀和的计算，假如，考虑一种情况，所有建筑的右边缘都是 $\infty$ ，而更新和查询就像前面分段树一样，都是取所有相关位置值的最大：也就是更新的时候扫描所有祖先节点，取其位置既有值和当前更新值的最大，查询的时候扫描所有前缀位置，取最大值，那么此时就可以用树状数组正确地更新高度和单点查询。

因为此时的更新要么不影响后面位置的高度，要么影响得都是建筑区间重叠的部分：

假设两栋建筑的区间分别为 $[l_0, \infty)$ 和 $[l_1, \infty)$ 高度分别为 $h_0$ 和 $h_1$ ，如果 $l_0 \neq l_1$ ，不妨令 $l_0 \lt l_1$ ，那么在 $[l_0, l_1)$ 的区间上，两者互不影响，因为这个区域只有 $l_0$ 的更新，而在 $[l_1, \infty)$ 的区域，两者本来就是区间重叠，用两个值中的最大值覆盖即可。这样在查询高度的时候，对于位置 $x$ ，如果 $x\in [l_0, l_1)$ ，那它的高度是 $h_0$ ，如果 $x\in [l_1, \infty)$ ，那它的高度是 $\max (h_0, h_1)$ 。

当然 $\infty$ 的情况既不可能，也无法计算，但是如果说所有建筑的右边缘都是重合的，都是 $r$ ，而所有超过 $r$ 的 $x$ 轴上的位置都不不需要查询，那么问题也是等价的。

那么回到当前问题，如果建筑能够按照右边缘的 $x$ 轴位置从右到左的顺序排列，然后我们从右向左扫描，只在扫描到建筑的右边缘时才把该建筑（所代表的一个区间的高度）更新到树状数组里，然后对扫描线位置进行高度查询，这样我们就可以确保所有建筑的右边缘都是重合的，并且不需要查询超过重合点之后的位置。

但是，但是，且不说我们的建筑是按照左边缘的从左到右的顺序排列的，关键问题是题目要求地关键点是按照从左到右扫描的顺序得到的，根本不能从右向左扫描，这要怎么解决呢？

于是有了这里比较Tricky地树状数组地构造³：

既然一定要从左向右扫描，我™ 😡直接从数组的尾部开始建立这个树状数组！

这样某个位置的高度就是它的后缀最大值，而它的祖先节点就在它的左边，从左向右扫描时就完美符合了前面假设得树状数组的适应情况！

反向树状数组

对于 base 1 的数组，$x$ 所辖区间长度是 x & (-x) ，而对于 base 0 的数组则是 (x+1) & -(x+1) ，对于从尾部建立起来的树状数组，$x’ = n - x - 1$ ，其中 $n$ 为数组长度。

树状数组更新的时候实际上只需要更新到扫描线的位置（也就是代码里的 until ）

class RevBIT():
    """Reversed Binary Indexed Tree"""

    def __init__(self, data_len: int):
        # base 0
        self.data = [0] * data_len

    def update(self, i: int, val: int, until: int) -> None:
        while i >= until:
            self.data[i] = max(self.data[i], val)

            i -= (len(self.data) - i - 1) & -(len(self.data) - i - 1)

    def suffix(self, i: int) -> int:
        acc = 0

        while True:
            acc = max(acc, self.data[i])

            l = (len(self.data) - i - 1) & -(len(self.data) - i - 1)
            if l == 0:
                break
            i += l

        return acc

总体过程

总体过程首先是 $x$ 轴坐标的排序和离散化，和前面分段树的处理一样，后面在扫描过程中更新建筑到树状数组上和即时地查询，显然对于每栋建筑，我们只需要更新建筑的右边缘的坐标⁴和高度。

from typing import *
from bisect import bisect_right


class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        return solve(buildings)


def solve(buildings: List[List[int]]) -> List[List[int]]:
    x_data = [buildings[0][0]]

    for (l, _, _) in buildings[1:]:
        if x_data[-1] != l:
            x_data.append(l)

    for (_, r, _) in buildings:
        i = bisect_right(x_data, r)

        if x_data[i-1] != r:
            x_data.insert(i, r)

    x_map = {x: i for i, x in enumerate(x_data)}

    bit = RevBIT(len(x_data))

    res = []
    j = 0

    for i, x in enumerate(x_data):
        while j < len(buildings) and x == buildings[j][0]:
            r, h = buildings[j][1:3]

            bit.update(x_map[r]-1, h, until=i)

            j += 1

        h = bit.suffix(x_map[x])

        if not res or res[-1][1] != h:
            res.append([x, h])

    return res

但是，在仔细考虑下我们对反向建构的树状数组的使用🤔，发现虽然我们扫描后缀，但只要一个位置来保存高度，而不需要真地计算前缀和，那么我们完全可以用一个普通的树状数组的结构，但是用父节点保存高度，更新的时候向前更新节点（查询扫描的逆过程，比如 $7 \rightarrow 6 \rightarrow 4 \rightarrow 2 \rightarrow 1$）⁵，查询的时候向后扫描所有父节点。

徒有其表的树状数组

class FakeBIT():
    """Fake Binary Indexed Tree whose prefix for update and suffix for query"""

    def __init__(self, data_len: int):
        # base 0
        self.data = [0] * data_len

    def update(self, i: int, val: int, until: int) -> None:
        while i >= until:
            self.data[i] = max(self.data[i], val)

            i -= (i + 1) & -(i + 1)

    def suffix(self, i: int) -> int:
        acc = 0

        while i < len(self.data):
            acc = max(acc, self.data[i])

            i += (i + 1) & -(i + 1)

        return acc

总体过程和反向树状数组一样，只需要把 bit = RevBIT(len(x_data)) 替换为 bit = FakeBIT(len(x_data))

解③：优先级队列

借着上文，我们从反向树状数组推到假树状数组，于是可以想到，为什么不干脆用优先级队列取代上面树状数组的作用？每次扫描的时候把把建筑更新到优先级队列里，保存一个右边缘坐标和高度，查询的时候就从对队首弹出所有右边缘不符合条件的元素，然后新的队首的元素的高度就是我们需要的该位置的最大高度，当然如果队列为空，就是高度为 $0$ 。

from typing import *
from bisect import insort
from sortedcontainers import SortedList


class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        return solve(buildings)


def solve(buildings: List[List[int]]) -> List[List[int]]:
    x_data = [l for (l, _, _) in buildings]

    for (_, r, _) in buildings:
        insort(x_data, r)

    queue = SortedList([], key=lambda x: x[1])
    i = 0
    res = []
    n_buildings = len(buildings)

    for x in x_data:
        while i < n_buildings and buildings[i][0] == x:
            queue.add((buildings[i][1], buildings[i][2]))
            i += 1

        # pop outdated from priority queue

        while queue and queue[-1][0] <= x:
            queue.pop()

        if queue:
            h = queue[-1][1]
        else:
            h = 0

        if not res or res[-1][1] != h:
            res.append([x, h])

    return res

sortedcontainers 是 LeetCode 承诺地自动包含进 Python 环境里的第三方库，它是一个纯 Python 但是足够高效地有序集合的库，只包含三个有序集合：SortedList，SortedSet，SortedDict ，用来补充标准库缺乏地功能。⁶⁷⁸

注解

python 3.10 ↩
只是在批量赋值和查询的时候有一个额外的求取最大值的操作，这是为了确保重叠区间的高度是上面所有建筑高度的最大值 ↩
我很欣赏这种设计，它就是非常清楚这个数据结构地构造和实质，然后就可以保留实质，根据需要随意地解构然后重构，这种使用可以说已入化境 ↩
当然准确说是 $r-1$ ↩
计算节点的关键是把握子区间的长度 ↩
但是我不得不吐槽得是，Python 作为曾经地号称“自带电池”地方便语言，但现在很多方面已经非常老迈（虽然正在尝试追赶），特别是相对于Rust而言，基本上如果不是为了比较不同实现的性能，出于方便考虑我宁可用 Rust ，Rust的问题就是优化太好、运行太快了，测试结果几乎总是 0 ms ，而 Python在这里的优势居然是足够慢，便于测试中能发现性能上的问题😅。 ↩
我真的为了寻找一个提供优先级队列功能地容器，花费了不少时间，Python 标准库里面有几个看起来很像地，但都不很合适，一个是 queue.PriorityQueue 名字就叫做优先级队列，但是是用来做进线程调度地😅；另一个是它的底层实现 heapq.[heapify, heappush, heappop] ，简直就和 C 语言的函数一样，可以传一个列表，然后构建基于堆地优先级队列，但是连个自定义 key 的功能都没有，还需要专门用一个数据包装，来自定义比较函数，实在绷不住；还有一个是 collections.OrderedDict 但它保持地是插入顺序。 ↩
但是第三方地 sortedcontainers.SortedList 也令人不太满意，首先方法非常简单，只供最基本地使用，另外实在不知道它加一些 not implemented，use xxx replace 的方法到实现里有什么好处，调用不存在的方法本来就会报错，又不需要它来做警戒哨，这只是在混淆代码的静态分析程序，让智能提示里出现错误地选项，让每个第一次使用它的人浪费几十秒的时间，去发现正确的方法😡。 ↩

0218 - The Skyline Problem

题干

破题

解①：分段树

Python 实现1

解②：树状数组

解③：优先级队列

注解

Python 实现¹