堆
- 天际线
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).
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], ...]
时间复杂度O(2n), 空间复杂度O(2n)
思路：使用正负号区分楼坐标的左和右，例如：[2, 9, 10]分解为 [2,-10], [9,10]，然后压入堆中，以x坐标为标准，然后依次取出最小成员，如果当前成员为左坐标，并且当前高度不是已知最高高度的话，将当前成员记录到最终结果中，然后将当前高度压入已知高度中；如果当前成员为右坐标，并且高度为已知最高高度，推出当前高度，将当前成员记录到最终结果中，如果非已知最高高度，不记录到最终结果，排除掉当前高度。
import heapq
def get_skyline(lrh):
que, live = [0], []
skyline = []
for l, r, h in lrh:
heapq.heappush(live, (l, -h))
heapq.heappush(live, (r, h))
while live:
res = heapq.heappop(live)
if res[1] < 0:
if res[1] < que[0]:
skyline.append([res[0], -res[1]])
heapq.heappush(que, res[1])
else:
if -res[1] == que[0]:
heapq.heappop(que)
skyline.append([res[0], -que[0]])
else:
que.remove(-res[1])
return skyline
if __name__ == "__main__":
lrh = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
assert get_skyline(lrh) == [[2, 10], [3, 15], [7, 12], [
12, 0], [15, 10], [20, 8], [24, 0]]
- 滑动窗口最大值
Given an array nums, there is a sliding window of size k
which is moving from the very left of the array to the very right.
You can only see the k numbers in the window.
Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].
def max_sliding_window(nums, k):
return [max(nums[index - k:index]) for index in range(k, len(nums) + 1)]
if __name__ == "__main__":
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
assert max_sliding_window(nums, k) == [3, 3, 5, 5, 6, 7]
