Skip to content

Latest commit

 

History

History
8 lines (8 loc) · 919 Bytes

LC-218.md

File metadata and controls

8 lines (8 loc) · 919 Bytes

城市天际线(不是)

题目链接:https://leetcode-cn.com/problems/the-skyline-problem/
给一堆矩阵的左右边界横坐标和高度,要求画出其轮廓(从左至右给出转折点和高度)
参考了官方题解,说的还是比较清楚的。
很直接的想法是针对每一个关键点给出其最高的高度,如果高度发生变化,将(该点坐标,对应高度)加入轮廓。这样需要遍历所有的边界点以及高度,时间复杂度是O(N)。
而优化的手段是减少判断高度所需要的点数,也就是只看包含边界点的矩形。先将所有左边界点小于等于该坐标的矩阵计入,然后删除右边界点小于该坐标的矩阵。也就是 判断区间是左闭右开的,因为到达右边缘后该矩阵的高度不再对后续的轮廓有影响。
另外对高度的判断用优先队列解决,保留最高的部分。