解锁SQL无限可能 | 如何利用SQL求解力扣难题接雨水问题?

2024-08-27 13:36

本文主要是介绍解锁SQL无限可能 | 如何利用SQL求解力扣难题接雨水问题?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1  需求描述

1 数据准备

2 问题分析

3 小结


1  需求描述

原文链接:42. 接雨水 - 力扣(LeetCode)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

1 数据准备

with rain_data as
(select array(0,1,0,2,1,0,1,3,2,1,2,1) height
)
select * from rain_data;

 

2 问题分析

本文为力扣第42题,属于hard级别。分析该问题的关键点在于"找规律,抓特征",这也是我专栏里一直提的核心技巧,语言不重要,重要的是思维方法,是算法逻辑,其余的工作只是利用语言去翻译,这一点对SQL语言尤为重要,因为语法简单的语言在实现上一定要重思维,重逻辑。

 这道题其实就是“木桶原理”,简单的说就是一个柱子能接多少水,取决于它两边“较短的板”。另外一个前提条件就是,两边的柱子高度都要比所要装水的柱子的高度要高,否则肯定是无法装水的。因此我们只需要关注左边最高的木板和右边最高的模板中较矮的一个就够了,那么存储的水,等于两边木板的较小值减去当前高度的值。用公式表示如下:

res[i] = min(l_max[i], r_max[i]) - height[i];

 我们将上述公式翻译成SQL语言即可:

第一步:先将数组展开成行

select tmp.pos + 1 id, tmp.height  heightfrom rain_datalateral view posexplode(height) tmp as pos, height

 第二步:求当前位置处,左最大与右最大

select  id, height, max(height) over(order by id) l_max, max(height) over(order by id desc) r_max
from(select tmp.pos + 1 id, tmp.height  heightfrom rain_datalateral view posexplode(height) tmp as pos, height)t;

 第三步:利用公式标记接雨水的柱子

select id,height,least(l_max,r_max) - height     as rain_flg
from
(select id, height, max(height) over (order by id)      l_max, max(height) over (order by id desc) r_maxfrom (select tmp.pos + 1 id, tmp.height  heightfrom rain_datalateral view posexplode(height) tmp as pos, height) t) t
order by id

 第四步:求出最终结果值。完整的SQL如下:

select sum(rain_flg)
from
(select least(max(tmp.height) over (order by id), max(tmp.height) over (order by id desc)) - tmp.height rain_flgfrom rain_data rlateral view posexplode(r.height) tmp as id, height) t

3 小结

本题给出上述结果,在SQL层面已经算完成了,SQL查询主要的任务就是关注特征,找出问题的特征,利用SQL提取出来就可以了,其优化方式和代码语言有所不同,对于写代码的形式,上述属于暴力求解,需要优化其两边搜所的效率,因此就会有双指针和动态规划的求解思路。虽然,但是,但对于本文一开始而言找出”木桶原理”的特征(res[i] = min(l_max[i], r_max[i]) - height[i]),也不是一件容易得事情,需要一定问题的分析能力。

关于此类如何找规律、抓特征这一思维技巧,我把他放在我的专栏数字化建设通关指南专栏里,并把所有的规律技巧整理在如下文章中,链接如下:

SQL很简单,可你却写不好?也许这才是SQL最好的教程-CSDN博客

这篇文章我将持续更新,欢迎关注并收藏,也欢迎向我提问题,我的公众号“会飞的一十六”也开通了,里面的内容和评论区也很精彩

这篇关于解锁SQL无限可能 | 如何利用SQL求解力扣难题接雨水问题?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1111816

相关文章

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》:本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL 衍生表(Derived Tables)的使用

《MySQL衍生表(DerivedTables)的使用》本文主要介绍了MySQL衍生表(DerivedTables)的使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学... 目录一、衍生表简介1.1 衍生表基本用法1.2 自定义列名1.3 衍生表的局限在SQL的查询语句select

MySQL 横向衍生表(Lateral Derived Tables)的实现

《MySQL横向衍生表(LateralDerivedTables)的实现》横向衍生表适用于在需要通过子查询获取中间结果集的场景,相对于普通衍生表,横向衍生表可以引用在其之前出现过的表名,本文就来... 目录一、横向衍生表用法示例1.1 用法示例1.2 使用建议前面我们介绍过mysql中的衍生表(From子句

六个案例搞懂mysql间隙锁

《六个案例搞懂mysql间隙锁》MySQL中的间隙是指索引中两个索引键之间的空间,间隙锁用于防止范围查询期间的幻读,本文主要介绍了六个案例搞懂mysql间隙锁,具有一定的参考价值,感兴趣的可以了解一下... 目录概念解释间隙锁详解间隙锁触发条件间隙锁加锁规则案例演示案例一:唯一索引等值锁定存在的数据案例二:

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。

MYSQL查询结果实现发送给客户端

《MYSQL查询结果实现发送给客户端》:本文主要介绍MYSQL查询结果实现发送给客户端方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql取数据和发数据的流程(边读边发)Sending to clientSending DataLRU(Least Rec

MySQL分区表的具体使用

《MySQL分区表的具体使用》MySQL分区表通过规则将数据分至不同物理存储,提升管理与查询效率,本文主要介绍了MySQL分区表的具体使用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、分区的类型1. Range partition(范围分区)2. List partition(列表分区)3. H