Question

218. 天际线问题

English Version

题目描述

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 _由这些建筑物形成的 天际线_ 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

• lefti 是第 i 座建筑物左边缘的 x 坐标。
• righti 是第 i 座建筑物右边缘的 x 坐标。
• heighti 是第 i 座建筑物的高度。

你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

 

示例 1：

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。

示例 2：

输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]

 

提示：

• 1 <= buildings.length <= 104
• 0 <= lefti < righti <= 231 - 1
• 1 <= heighti <= 231 - 1
• buildings 按 lefti 非递减排序

解法

方法一：扫描线+优先队列

记录下所有建筑物的左右边界线，升序排序之后得到序列 lines。对于每一个边界线 lines[i]，找出所有包含 lines[i] 的建筑物，并确保建筑物的左边界小于等于 lines[i]，右边界大于 lines[i]，则这些建筑物中高度最高的建筑物的高度就是该线轮廓点的高度。可以使用建筑物的高度构建优先队列（大根堆），同时需要注意高度相同的轮廓点需要合并为一个。

from queue import PriorityQueue


class Solution:
  def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
    skys, lines, pq = [], [], PriorityQueue()
    for build in buildings:
      lines.extend([build[0], build[1]])
    lines.sort()
    city, n = 0, len(buildings)
    for line in lines:
      while city < n and buildings[city][0] <= line:
        pq.put([-buildings[city][2], buildings[city][0], buildings[city][1]])
        city += 1
      while not pq.empty() and pq.queue[0][2] <= line:
        pq.get()
      high = 0
      if not pq.empty():
        high = -pq.queue[0][0]
      if len(skys) > 0 and skys[-1][1] == high:
        continue
      skys.append([line, high])
    return skys

class Solution {
public:
  vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
    set<int> poss;
    map<int, int> m;
    for (auto v : buildings) {
      poss.insert(v[0]);
      poss.insert(v[1]);
    }

    int i = 0;
    for (int pos : poss)
      m.insert(pair<int, int>(pos, i++));

    vector<int> highs(m.size(), 0);
    for (auto v : buildings) {
      const int b = m[v[0]], e = m[v[1]];
      for (int i = b; i < e; ++i)
        highs[i] = max(highs[i], v[2]);
    }

    vector<pair<int, int>> res;
    vector<int> mm(poss.begin(), poss.end());
    for (int i = 0; i < highs.size(); ++i) {
      if (highs[i] != highs[i + 1])
        res.push_back(pair<int, int>(mm[i], highs[i]));
      else {
        const int start = i;
        res.push_back(pair<int, int>(mm[start], highs[i]));
        while (highs[i] == highs[i + 1])
          ++i;
      }
    }
    return res;
  }
};

type Matrix struct{ left, right, height int }
type Queue []Matrix

func (q Queue) Len() int       { return len(q) }
func (q Queue) Top() Matrix    { return q[0] }
func (q Queue) Swap(i, j int)    { q[i], q[j] = q[j], q[i] }
func (q Queue) Less(i, j int) bool { return q[i].height > q[j].height }
func (q *Queue) Push(x any)    { *q = append(*q, x.(Matrix)) }
func (q *Queue) Pop() any {
  old, x := *q, (*q)[len(*q)-1]
  *q = old[:len(old)-1]
  return x
}

func getSkyline(buildings [][]int) [][]int {
  skys, lines, pq := make([][]int, 0), make([]int, 0), &Queue{}
  heap.Init(pq)
  for _, v := range buildings {
    lines = append(lines, v[0], v[1])
  }
  sort.Ints(lines)
  city, n := 0, len(buildings)
  for _, line := range lines {
    // 将所有符合条件的矩形加入队列
    for ; city < n && buildings[city][0] <= line && buildings[city][1] > line; city++ {
      v := Matrix{left: buildings[city][0], right: buildings[city][1], height: buildings[city][2]}
      heap.Push(pq, v)
    }
    // 从队列移除不符合条件的矩形
    for pq.Len() > 0 && pq.Top().right <= line {
      heap.Pop(pq)
    }
    high := 0
    // 队列为空说明是最右侧建筑物的终点，其轮廓点为 (line, 0)
    if pq.Len() != 0 {
      high = pq.Top().height
    }
    // 如果该点高度和前一个轮廓点一样的话，直接忽略
    if len(skys) > 0 && skys[len(skys)-1][1] == high {
      continue
    }
    skys = append(skys, []int{line, high})
  }
  return skys
}

impl Solution {
  pub fn get_skyline(buildings: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut skys: Vec<Vec<i32>> = vec![];
    let mut lines = vec![];
    for building in buildings.iter() {
      lines.push(building[0]);
      lines.push(building[1]);
    }
    lines.sort_unstable();
    let mut pq = std::collections::BinaryHeap::new();
    let (mut city, n) = (0, buildings.len());

    for line in lines {
      while city < n && buildings[city][0] <= line && buildings[city][1] > line {
        pq.push((buildings[city][2], buildings[city][1]));
        city += 1;
      }
      while !pq.is_empty() && pq.peek().unwrap().1 <= line {
        pq.pop();
      }
      let mut high = 0;
      if !pq.is_empty() {
        high = pq.peek().unwrap().0;
      }
      if !skys.is_empty() && skys.last().unwrap()[1] == high {
        continue;
      }
      skys.push(vec![line, high]);
    }
    skys
  }
}