218.天际线问题

链接：218.天际线问题
难度：Hard
标签：树状数组、线段树、数组、分治、有序集合、扫描线、堆（优先队列）
简介：城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。

题解 1 - typescript

• 编辑时间：2021-07-13
• 执行用时：392ms
• 内存消耗：46.2MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/the-skyline-problem/solution/js-sao-miao-xian-fa-jian-dan-yi-dong-by-fleetingso/)。

function getSkyline(buildings: number[][]): number[][] {
  const list: [number, number][] = [];
  buildings.forEach(([l, r, h]) => list.push([l, -h], [r, h]));
  list.sort(([i1, h1], [i2, h2]) => (i1 === i2 ? h1 - h2 : i1 - i2));
  const heights: number[] = [0];
  const remove = (h: number) => {
    for (let i = 0, l = heights.length; i < l; i++)
      if (heights[i] === h) {
        heights.splice(i, 1);
        return;
      }
  };
  let ans: number[][] = [];
  let preH: number | null = null;
  for (const [idx, h] of list) {
    if (h < 0) heights.push(-h);
    else remove(h);
    let maxH = Math.max(...heights);
    if (preH !== maxH) ans.push([idx, (preH = maxH)]);
  }
  return ans;
}