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

newkid

暴力法：用连接，检查每个建筑物的起点终点上，找到这些点上面存在的最高的建筑物高度。如果连续多个点的高度不变，输出的时候要合并，只输出第一个。
with b as ( ---- 每个建筑物拆开成起点和终点两行数据
select distinct case when flag='START' then start_pos else end_pos end as pos
  from buildings cross join (select 'START' flag from dual union all select 'END' from dual)
)
select min(pos) as pos
      ,h2
  from (
        select pos
              ,h2
               ,row_number() over(order by pos) rn1
               ,row_number() over(partition by h2 order by pos) rn2
          from (
                select b.pos
                      ,nvl(max(b2.height),0) h2
                  from b left join buildings b2
                       on b.pos>=b2.start_pos and b.pos<b2.end_pos
                  group by b.pos
               )
        )
group by rn1-rn2,h2
order by 1;

也可以用标量子查询代替自连接：
with b as (
select distinct case when flag='START' then start_pos else end_pos end as pos
  from buildings cross join (select 'START' flag from dual union all select 'END' from dual)
)
select min(pos) as pos
      ,h2
  from (
        select pos
              ,h2
               ,row_number() over(order by pos) rn1
               ,row_number() over(partition by h2 order by pos) rn2
          from (
                select b.pos
                      ,nvl((select max(height) from buildings b2 where b2.start_pos<=b.pos and b2.end_pos>b.pos),0) h2
                  from b
               )
        )
group by rn1-rn2,h2
order by 1;

      POS         H2
--------- ----------
        2         10
        3         15
        7         12
       12          0
       15         10
       20          8
       24          0



7 rows selected.

--------match recognize: 依然是检查每个起点终点(记为strt)，和它之后出现的每个建筑物终点end_p进行匹配(之后出现的起点不会影响轮廓线，不用理会), 如果这个end_p的起点在strt之前就取其高度。
with b as ( ---- 每个建筑物拆开成起点和终点两行数据
select buildings.*
      ,case when flag='START' then start_pos else end_pos end as pos
      ,flag
  from buildings cross join (select 'START' flag from dual union all select 'END' from dual)
)
,b2 as (
select * from b
     match_recognize (
     order by pos
     measures
        strt.pos as pos
       ,final max(end_p.height) as h2
     one row per match
     after match skip to next row  ----- 一个strt匹配结束之后跳到下一个点
     pattern( strt (end_p | other_p)*)
     define end_p as flag='END' and pos>strt.pos and start_pos<=strt.pos
     )
)
select pos,nvl(h2,0) as h2   ---如果多个点有同样高度，去重复
  from b2
     match_recognize (
     order by pos
     measures
          first(pos) as pos
         ,first(h2) as h2        
     one row per match
     pattern( strt dup*)
     define dup as h2 = prev(h2)
     )
;

       POS         H2
---------- ----------
         2         10
         3         15
         7         12
        12          0
        15         10
        20          8
        24          0

7 rows selected.

〇〇

newkid 发表于 2024-9-22 06:45
暴力法：用连接，检查每个建筑物的起点终点上，找到这些点上面存在的最高的建筑物高度。如果连续多个点的高 ...

你的第一种

Run Time (s): real 2.395 user 4.578125 sys 0.093750
第二种
Run Time (s): real 4.094 user 4.046875 sys 0.000000
我的
Run Time (s): real 5.333 user 10.046875 sys 0.015625

〇〇

bu.rar (69.05 KB, 下载次数: 6)

2024-9-22 07:34 上传

点击文件名下载附件

测试数据

newkid

〇〇 发表于 2024-9-22 07:32
你的第一种 Run Time (s): real 2.395 user 4.578125 sys 0.093750第二种Run Time (s): real 4.094 user 4. ...

什么库？match_recognize 也支持？

〇〇

newkid 发表于 2024-9-22 08:15
什么库？match_recognize 也支持？

duckdb,不支持match_recognize