解决“天际线问题”的Python程序

Question

这是一个Leetcode问题 -

从远处看，城市的天际线是由城市内所有建筑物形成的轮廓的外部轮廓。现在，假设您得到了所有建筑物的位置和高度，如城市景观照片(图A)所示，编写一个程序来输出由这些建筑物共同形成的天际线(图B)。

每座建筑物的几何信息都是由三重整数[Li, Ri, Hi]__表示的，其中Li和Ri分别是i__th大楼左右边的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中的红色点)。关键点是水平线segment__的左端点。请注意，最后一个关键点，也就是最右边的建筑物的尽头，只是用来标记天际线的尽头，并且总是有零高度。此外，任何两个相邻建筑物之间的地面应视为天际线轮廓的一部分。例如，图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], ...]__。

下面是我对这个任务的解决方案，使用(在Python中)-

class Solution: def get\_skyline(self, buildings): """ :type buildings: List[List[int]] :rtype: List[List[int]] """ if not buildings: return [] if len(buildings) == 1: return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]] mid = len(buildings) // 2 left = self.get\_skyline(buildings[:mid]) right = self.get\_skyline(buildings[mid:]) return self.merge(left, right) def merge(self, left, right): h1, h2 = 0, 0 i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i][0] < right[j][0]: h1 = left[i][1] corner = left[i][0] i += 1 elif right[j][0] < left[i][0]: h2 = right[j][1] corner = right[j][0] j += 1 else: h1 = left[i][1] h2 = right[j][1] corner = right[j][0] i += 1 j += 1 if self.is\_valid(result, max(h1, h2)): result.append([corner, max(h1, h2)]) result.extend(right[j:]) result.extend(left[i:]) return result def is\_valid(self, result, new\_height): return not result or result[-1][1] != new\_height

下面是一个输出示例-

#output = Solution()
#print(output.get_skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]))

>>> [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

这是输出所需的时间-

%timeit output.get_skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]])
>>> 27.6 µs ± 3.65 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

因此，我想知道我是否可以使这个程序更有效和/或更短。任何选择都是受欢迎的。

Answer 1

不错的方法。

这是一个很难分析运行时间的问题，因为输出大小是可变的。merge的运行时间与其输入的总大小成线性关系，这是子问题的输出大小。我们可以说，基例为一个输入点生成两个点，而merge不创建新的点，因此合并的点数最多是输入点数的两倍。因此，递归是T(n) = 2T(n/2) + O(n)，它是给出O(n \lg n)的标准递推。

我们也可以证明，这是不可能通过减少排序。给出要排序的集合\{x_i\}，求出最大m并构造\{(0, m + 1 - x_i, x_i)\}。输出将给出按降序排序的x_i。

所以你的方法是渐近最优的，而且很优雅。合并没有任何花哨，所以它应该有一个低常数隐藏的大-O表示法。

我认为一些双索引数组访问可以从引入名称中获益。特别是，我会发现

return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

更具可读性

l, r, h = buildings[0] return [[l, h], [r, 0]]

merge中的这三种情况可以用<=大大简化。我发现is_valid不优雅，所以我会通过跟踪“当前”高度来消除它。介绍left[i][0]和right[j][0]的名称--我将代码重构为

def merge(self, left, right): h1, h2, hcurrent = 0, 0, 0 i, j = 0, 0 result = [] while i < len(left) and j < len(right): x0 = left[i][0] x1 = right[j][0] if x0 <= x1: h1 = left[i][1] i += 1 if x1 <= x0: h2 = right[j][1] j += 1 if max(h1, h2) != hcurrent: hcurrent = max(h1, h2) result.append([min(x0, x1), hcurrent]) result.extend(right[j:]) result.extend(left[i:]) return result

另一种办法是重新考虑使用哨兵，如：

def merge(self, left, right): h1, h2 = 0, 0 i, j = 0, 0 result = [[0, 0]] while i < len(left) and j < len(right): x0 = left[i][0] x1 = right[j][0] if x0 <= x1: h1 = left[i][1] i += 1 if x1 <= x0: h2 = right[j][1] j += 1 if max(h1, h2) != result[-1][1]: result.append([min(x0, x1), max(h1, h2)]) result.extend(right[j:]) result.extend(left[i:]) return result[1:]

不管是哪种情况，我认为最好加上一条解释为什么

result.extend(right[j:]) result.extend(left[i:])

不需要任何额外的检查，以避免在同一高度产生连续两个点。

Answer 2

除了现有的彼得泰勒的伟大答案，我想补充一些关于方法与自由函数的想法。

Python是一种多范式语言。它专注于，但不仅仅是面向对象的编程。当然，可以构造一个包含所有方法的大型Solution类，但它可能不是最好的解决方案。(H)

作为一般指导原则，您可以使用类将数据和作用于该数据的函数组合在一起。如果您只是想将函数组合到一个名称空间中，那么应该使用名称空间，即python中的模块。

让我们具体了解一下您的is_valid方法。它从不使用自我。如果希望保持类结构，则至少应将其显式化，并将其更改为：

@staticmethod
def is_valid(result, new_height):

staticmethod基本上是驻留在类的命名空间中的一个自由函数。

但是(固执己见)在可重用性方面，完全“免费”您的功能可能会更好。如果您来自C++背景，这使您觉得它就像一个模板函数，可以独立于Solution类在不同的输入上应用。

如果您“释放”了is_valid，您就会意识到，merge也不依赖于self，如果您“释放”了merge，您将最终意识到get_skyline基本上是一个调用merge的递归函数，可以是一个staticmethod或一个自由函数本身。

最后，您将得到一个包含三个静态方法的类，即一个具有三个空闲函数的名称空间。实现这一结构的规范方法是在自己的模块中拥有这三个功能，即它们自己的文件。

实际上，只需删除class和对self的引用，减少方法并调用文件Solutions.py。然后你就可以打电话了

import Solutions
Solutions.get_skyline(my_cool_skyline_test_data)

在语法方面，这与类方法非常相似，但却使函数彼此解耦。

如果您认为像is_valid这样的函数是模块的实现细节，那么您可以在下划线前面加上一个下划线，这使得它按照约定是私有的。这将允许在_is_valid函数和另一个答案中建议的手动“当前”高度跟踪之间切换。