趣味SQL: 力扣218. 天际线问题

newkid

原题链接

[color=var(--text-primary)]218. 天际线问题




[color=var(--difficulty-hard)][backcolor=var(--fill-secondary)]困难
[color=hsl(var(--sd-secondary-foreground))][backcolor=var(--fill-secondary)]
相关标签
[color=hsl(var(--sd-secondary-foreground))][backcolor=var(--fill-secondary)]相关企业
[color=hsl(var(--sd-secondary-foreground))][backcolor=var(--fill-secondary)]

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

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings = [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：

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

示例 2：

[color=rgb(38 38 38/var(--tw-text-opacity))]输入：buildings = [[0,2,3],[2,5,3]][color=rgb(38 38 38/var(--tw-text-opacity))]输出：[[0,3],[5,0]]

提示：

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

newkid

create table buildings (
    start_pos number
   ,end_pos number
   ,height number
   );

delete buildings;
insert into buildings
select 2,9,10 from dual     
union all select 3,7,15    from dual
union all select 5,12,12   from dual
union all select 15,20,10  from dual
union all select 19,24,8   from dual
;

〇〇

先把整个坐标系的x对应y填上0，然后把每个矩形对应的x高度填上，轮廓线就出来了

〇〇

就是x很长的时候比较浪费
with t as(
select unnest( range(0,mx)) i,0 from (select max(end_pos)+1 mx from buildings)
)
,a as(select i, max(height) maxh from t left join buildings
on i between start_pos and end_pos-1
group by i
order by i
)
select i,height from (
select i,coalesce(maxh,0)height,case when coalesce(lag(maxh)over(order by i),0)=coalesce(maxh,0) then 1 else 0 end flag from a
)where flag=0
;

〇〇

10000个建筑
insert into buildings
select least(a,b),greatest(a,b),c from(
select (random()*100000)::int % 10000+1 a, (random()*100000)::int % 10000+1 b, (random()*100000)::int % 10000+1 c from range(10000))
where a<>b;

┌───────┬────────┐
│   i   │ height │
│ int64 │ int32  │
├───────┼────────┤
│     1 │   4531 │
│     3 │   9009 │
│     8 │   9990 │
│   156 │  10000 │
│  8280 │   9996 │
│  8886 │   9995 │
│  9976 │   9945 │
│  9981 │   9529 │
│  9988 │   9386 │
│  9997 │   9100 │
│  999 8 │   8009 │
│ 10000 │      0 │
├───────┴────────┤
│    12 rows     │
└────────────────┘
Run Time (s): real 2.163 user 2.683217 sys 0.062400

newkid

你这方法不支持小数

〇〇

我这不但不支持小数，而且太费空间

〇〇

思路2，每次加入一个矩形时，判断左右上端点是否在已有的天际线下，如果不是，把其中突出来的加入天际线

newkid

思路对头，把它写出来。

〇〇

看到一个相关的帖子 https://mp.weixin.qq.com/s/0M5RN4a_bRxyQoZdJQoKJA