Leetcode 218 The Skyline Problem
最编程
2024-10-05 19:55:28
...
https://leetcode.com/problems/the-skyline-problem/description/
题意,给定一个array的vector, [2,9, 10](代表从2-9这个区间内我有一个10的大楼),我需要求出这个城市的天际线(描边)
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
output [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
首先第一个思想:
我要描边,什么时候会有这个需求?肯定是我的高度发生改变的时候需要记录下来
非常容易想到扫描线算法,确定event上升沿下降沿,并且用一个数据结构去维护此时的最大值,但是这个数据结构还要有一定的快速删除的能力,所以用multiset
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> ret;
vector<pair<int, int>> events;
for (auto& b : buildings) {
events.push_back({b[0], -b[2]});
events.push_back({b[1], b[2]});
}
sort(events.begin(), events.end());
int prevH = 0;
multiset<int> height;
height.insert(0);
for(auto& [x,h]: events) {
if (h < 0) {
height.insert(-h);
} else {
height.erase(height.find(h));
}
int currentH = *height.rbegin();
if(currentH != prevH) {
ret.push_back({x,currentH});
prevH = currentH;
}
}
return ret;
}
};
推荐阅读
-
Leetcode 218 The Skyline Problem
-
C++ | Leetcode C++ 问题解决 Question 448 Find all the disappearing numbers in the array - Problem Solved:
-
C++ | Leetcode C++ Problem Solver for Problem 239 Sliding Window Maximum - Problem Solver:
-
Golang | Leetcode Golang 问题解决 #234 Backtracking Chained Tables - Problem Solved:
-
Java | Leetcode Java 问题解决 Question 63 Different Paths II - Problem Solving:
-
Backtracking Approach for LeetCode Problem 679: 24 Game