上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
}
};
python3 解法, 执行用时: 104 ms, 内存消耗: 21.7 MB, 提交时间: 2023-09-05 10:28:45
from sortedcontainers import SortedList
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
ans = []
# 预处理所有的点，为了方便排序，对于左端点，令高度为负；对于右端点令高度为正
ps = []
for l, r, h in buildings:
ps.append((l, - h))
ps.append((r, h))
# 先按照横坐标进行排序
# 如果横坐标相同，则按照左端点排序
# 如果相同的左/右端点，则按照高度进行排序
ps.sort()
prev = 0
# 有序列表充当大根堆
q = SortedList([prev])
for point, height in ps:
if height < 0:
# 如果是左端点，说明存在一条往右延伸的可记录的边，将高度存入优先队列
q.add(-height)
else:
# 如果是右端点，说明这条边结束了，将当前高度从队列中移除
q.remove(height)
# 取出最高高度，如果当前不与前一矩形“上边”延展而来的那些边重合，则可以被记录
cur = q[-1]
if cur != prev:
ans.append([point, cur])
prev = cur
return ans
cpp 解法, 执行用时: 28 ms, 内存消耗: 13.5 MB, 提交时间: 2023-09-05 10:28:26
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) -> bool { return a.second < b.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> que(cmp);
vector<int> boundaries;
for (auto& building : buildings) {
boundaries.emplace_back(building[0]);
boundaries.emplace_back(building[1]);
}
sort(boundaries.begin(), boundaries.end());
vector<vector<int>> ret;
int n = buildings.size(), idx = 0;
for (auto& boundary : boundaries) {
while (idx < n && buildings[idx][0] <= boundary) {
que.emplace(buildings[idx][1], buildings[idx][2]);
idx++;
}
while (!que.empty() && que.top().first <= boundary) {
que.pop();
}
int maxn = que.empty() ? 0 : que.top().second;
if (ret.size() == 0 || maxn != ret.back()[1]) {
ret.push_back({boundary, maxn});
}
}
return ret;
}
};
java 解法, 执行用时: 16 ms, 内存消耗: 45.1 MB, 提交时间: 2023-09-05 10:27:27
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
List<Integer> boundaries = new ArrayList<Integer>();
for (int[] building : buildings) {
boundaries.add(building[0]);
boundaries.add(building[1]);
}
Collections.sort(boundaries);
List<List<Integer>> ret = new ArrayList<List<Integer>>();
int n = buildings.length, idx = 0;
for (int boundary : boundaries) {
while (idx < n && buildings[idx][0] <= boundary) {
pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
idx++;
}
while (!pq.isEmpty() && pq.peek()[0] <= boundary) {
pq.poll();
}
int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
if (ret.size() == 0 || maxn != ret.get(ret.size() - 1).get(1)) {
ret.add(Arrays.asList(boundary, maxn));
}
}
return ret;
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 6.7 MB, 提交时间: 2023-09-05 10:27:15
// 扫描线 + 优先队列
type pair struct{ right, height int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].height > h[j].height }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func getSkyline(buildings [][]int) (ans [][]int) {
n := len(buildings)
boundaries := make([]int, 0, n*2)
for _, building := range buildings {
boundaries = append(boundaries, building[0], building[1])
}
sort.Ints(boundaries)
idx := 0
h := hp{}
for _, boundary := range boundaries {
for idx < n && buildings[idx][0] <= boundary {
heap.Push(&h, pair{buildings[idx][1], buildings[idx][2]})
idx++
}
for len(h) > 0 && h[0].right <= boundary {
heap.Pop(&h)
}
maxn := 0
if len(h) > 0 {
maxn = h[0].height
}
if len(ans) == 0 || maxn != ans[len(ans)-1][1] {
ans = append(ans, []int{boundary, maxn})
}
}
return
}
