LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 先保存每个建筑的顶点，把所有顶点按横坐标升序排列。为了区分左右顶点，把左顶点的高度标记为负数

[[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
          _______ 
15       |       |
14       |       |
13       |    ___|_________
12       |   |   |         |
11      _|___|___|___      |      _________
10     | |   |   |   |     |     |         |
9      | |   |   |   |     |     |        _|_______
8      | |   |   |   |     |     |       | |       |
7      | |   |   |   |     |     |       | |       |
6      | |   |   |   |     |     |       | |       |
5      | |   |   |   |     |     |       | |       |
4      | |   |   |   |     |     |       | |       |
3      | |   |   |   |     |     |       | |       |
2      | |   |   |   |     |     |       | |       |
1      | |   |   |   |     |     |       | |       |
0  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

顶点为
[2, -10] [3, -15] [5, -12] [7, 15] [9, 10] [12, 12] [15, -10] [19, -8] [20, 10] [24, 8]

• 用一个队列来保存左顶点高度。从左到右遍历顶点，如果是左顶点则将高度推入队列，如果是右顶点，则删除其对应的左顶点的高度，原因是左顶点的最高高度才能产生天际线，而右顶点是左顶点能生成的天际线的终点，因此应删除其高度。每次遍历后，如果剩余左顶点的最高高度与上一次不同，则说明这是一个转折点

[2, -10] [3, -15] [5, -12] [7, 15] [9, 10] [12, 12] [15, -10] [19, -8] [20, 10] [24, 8]

队列初始化 => 0（用于保存最后一个顶点，因为最后一个顶点高度必然为 0）

[2, -10] => 0 10
mx = 10，与上一次不同，把该点的横坐标及最大高度 [2, 10] 添加到结果
res = [2, 10]

[3, -15] => 0 10 15
mx = 15，与上一次不同，把该点的横坐标及最大高度 [3, 15] 添加到结果
res = [2, 10] [3, 15]

[5, -12] => 0 10 12 15
mx = 15，与上一次相同，说明新点高度低于已有高度，该点被覆盖，无需添加
res = [2, 10] [3, 15]

[7, 15] => 0 10 12
mx = 12，与上一次不同，把该点的横坐标及最大高度 [7, 12] 添加到结果
res = [2, 10] [3, 15] [7, 12]

[9, 10] => 0 12
mx = 12，与上一次相同，说明新点高度低于已有高度，该点被覆盖，无需添加
res = [2, 10] [3, 15] [7, 12]

[12, 12] => 0
mx = 0，与上一次不同，把该点的横坐标及最大高度 [12, 0] 添加到结果
res = [2, 10] [3, 15] [7, 12] [12, 0]

[15, -10] => 0 10
mx = 10，与上一次不同，把该点的横坐标及最大高度 [15, 10] 添加到结果
res = [2, 10] [3, 15] [7, 12] [12, 0] [15, 10]

[19, -8] => 0 8 10
mx = 10，与上一次相同，说明新点高度低于已有高度，该点被覆盖，无需添加

[20, 10] => 0 8
mx = 8，与上一次不同，把该点的横坐标及最大高度 [20, 8] 添加到结果
res = [2, 10] [3, 15] [7, 12] [12, 0] [20, 8]

[24, 8] => 0
mx = 0，与上一次不同，把该点的横坐标及最大高度 [24, 0] 添加到结果
res = [2, 10] [3, 15] [7, 12] [12, 0] [20, 8] [24, 0]

• 实现如下

class Solution {
 public:
  vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<vector<int>> res;
    multiset<pair<int, int>> s;
    for (auto& x : buildings) {
      s.emplace(x[0], -x[2]);  // 标记为负以用于之后区分左右顶点
      s.emplace(x[1], x[2]);
    }
    multiset<int> m{0};
    int pre = 0;
    int mx = 0;
    for (auto& [x, y] : s) {  // C++17 结构化绑定语法
      if (y < 0) {
        m.emplace(-y);
      } else {
        m.erase(m.find(y));  // 只删除 multiset 的一个元素，所以要用 find
      }
      mx = *rbegin(m);
      if (mx != pre) {
        res.emplace_back(vector<int>{x, mx});
        pre = mx;
      }
    }
    return res;
  }
};