原题
水平面上有 N 座大楼，每座大楼都是矩阵的形状，可以用三个数字表示 (start, end, height)，分别代表其在x轴上的起点，终点和高度。大楼之间从远处看可能会重叠，求出N 座大楼的外轮廓线。
外轮廓线的表示方法为若干三元组，每个三元组包含三个数字 (start, end, height)，代表这段轮廓的起始位置，终止位置和高度。
样例
给出三座大楼：
[
[1, 3, 3],
[2, 4, 4],
[5, 6, 1]
]
外轮廓线为：
[
[1, 2, 3],
[2, 4, 4],
[5, 6, 1]
]
解题思路
- Sweep-Line - 扫描线问题，可以每次移动一个非常小的单位，不断去求当下楼房的高度。但实际上，只有某个楼房的开始或结尾才有交点的变化。
- 第一步，拆分(1, 3, 3) => (1, 3, 起点) 和 (3, 3, 终点)，然后排序，关于排序，对于含有坐标，高度，始末标记的三元组
- 首先按坐标排序(大小排序)
- 坐标一样时，按高度排序(大小排序)
- 高度也一样时，按始末排序，始 > 末
- 排序非常重要， 时间复杂度是O(nlogn)
- 每次到交点的时候，要求几个楼房的高度最大值 - Heap
- 每次到某一个楼房终点的时候要从堆中删除相应的高度 - HashHeap 时间复杂度是O(nlogn)
- 时间复杂度 O(nlogn) + O(nlogn) => O(nlogn)
- 如何查看堆顶元素
myheap.queue[0]
完整代码
class node:
"""
create a node class to handle the duplicates in heap.
id => the index of x, num = number of x in heap
"""
def __init__(self, id, number):
self.id = id
self.num = number
class HashHeap:
def __init__(self):
self.map = {}
self.hashmaxheap = [0]
self.map[0] = node(0, 1)
self.currentSize = 0
def put(self, data):
"""add a new item to the hashmaxheap"""
if data in self.map:
existData = self.map[data]
self.map[data] = node(existData.id, existData.num + 1)
self.currentSize += 1
return
else:
self.hashmaxheap.append(data)
self.map[data] = node(len(self.hashmaxheap) - 1, 1)
self.currentSize += 1
self.siftUp(len(self.hashmaxheap) - 1)
def peek(self):
"""returns the item with the maxmum key value"""
return self.hashmaxheap[1]
def get(self):
"""returns the item with the maxmum key value, removing the item from the heap"""
res = self.hashmaxheap[1]
if self.map[res].num == 1:
if self.map[res].id == len(self.hashmaxheap) - 1:
del self.map[res]
self.hashmaxheap.pop()
self.currentSize -= 1
return res
del self.map[res]
self.hashmaxheap[1] = self.hashmaxheap[-1]
self.map[self.hashmaxheap[1]] = node(1, self.map[self.hashmaxheap[1]].num)
self.hashmaxheap.pop()
self.siftDown(1)
else:
self.map[res] = node(1, self.map[res].num - 1)
self.currentSize -= 1
return res
def delete(self, data):
existData = self.map[data]
if existData.num == 1:
del self.map[data]
if existData.id == len(self.hashmaxheap) - 1:
self.hashmaxheap.pop()
self.currentSize -= 1
return
self.hashmaxheap[existData.id] = self.hashmaxheap[-1]
self.map[self.hashmaxheap[-1]] = node(existData.id, self.map[self.hashmaxheap[-1]].num)
self.hashmaxheap.pop()
self.siftUp(existData.id)
self.siftDown(existData.id)
else:
self.map[data] = node(existData.id, existData.num - 1)
self.currentSize -= 1
def siftUp(self, index):
# // means devide by 2 and return int
while index // 2 > 0:
if self.hashmaxheap[index] < self.hashmaxheap[index // 2]:
break
else:
numA = self.map[self.hashmaxheap[index]].num
numB = self.map[self.hashmaxheap[index // 2]].num
self.map[self.hashmaxheap[index]] = node(index // 2, numA)
self.map[self.hashmaxheap[index // 2]] = node(index, numB)
self.hashmaxheap[index], self.hashmaxheap[index // 2] = self.hashmaxheap[index // 2], self.hashmaxheap[index]
index = index // 2
def siftDown(self, index):
"""correct single violation in a sub-tree"""
if index > (len(self.hashmaxheap) - 1) // 2:
return
# find the max child of current index
if (index * 2 + 1) > (len(self.hashmaxheap) - 1) or self.hashmaxheap[index * 2] > self.hashmaxheap[index * 2 + 1]:
maxChild = index * 2
else:
maxChild = index * 2 + 1
if self.hashmaxheap[index] > self.hashmaxheap[maxChild]:
return
else:
numA = self.map[self.hashmaxheap[index]].num
numB = self.map[self.hashmaxheap[maxChild]].num
self.map[self.hashmaxheap[index]] = node(maxChild, numA)
self.map[self.hashmaxheap[maxChild]] = node(index, numB)
self.hashmaxheap[index], self.hashmaxheap[maxChild] = self.hashmaxheap[maxChild], self.hashmaxheap[index]
self.siftDown(index * 2)
self.siftDown(index * 2 + 1)
def size(self):
return self.currentSize
def isEmpty(self):
return self.currentSize == 0
def sorter(x, y):
if x[0] != y[0]:
return x[0] - y[0]
elif x[1] != y[1]:
return x[1] - y[1]
# 相同时间点上，加入新楼有优先权
return y[2] - x[2]
class Solution:
# @param buildings: A list of lists of integers
# @return: A list of lists of integers
def buildingOutline(self, buildings):
# write your code here
if len(buildings) == 0:
return []
timepoints = [] # pos, height, in/out
for building in buildings:
timepoints.append((building[0], building[2], 1))
timepoints.append((building[1], building[2], -1))
timepoints = sorted(timepoints, cmp=sorter)
heights = HashHeap()
left = 1
res = []
for timepoint in timepoints:
if timepoint[2] == 1:
if heights.isEmpty() or timepoint[1] > heights.peek():
if timepoint[0] != left and not heights.isEmpty():
res.append([left, timepoint[0], heights.peek()])
left = timepoint[0]
heights.put(timepoint[1])
else:
heights.delete(timepoint[1])
if heights.isEmpty() or timepoint[1] > heights.peek():
res.append([left, timepoint[0], timepoint[1]])
left = timepoint[0]
return res
网友评论