网站首页 > 技术文章 正文
大家好,今天给大家分享一道经典面试题接雨水(trapping-rain-water)。
题目要求:
给定 n个非负整数表示每个宽度为 1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
难度: 困难
示例 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
题解:
关键思想:双指针。
我们可以使用两个指针,一个指向左边的柱子,一个指向右边的柱子。然后我们可以逐渐将指针向中间移动,同时维护左边和右边的最大高度。在移动指针的过程中,如果左边的最大高度小于右边的最大高度,则说明左边可以接到水,反之则说明右边可以接到水。我们可以将左边或右边的指针向中间移动一步,并将左边或右边的最大高度更新为当前指针所指的柱子高度。
下面是具体的算法步骤:
- 初始化左指针left=0,右指针right=n-1,左边最大高度left_max=0,右边最大高度right_max=0,水的容量volume=0。
- 当left<=right时,执行以下步骤: a. 如果left_max<right_max,则说明左边可以接到水,计算当前位置能接的水量并加入volume,然后将左指针向中间移动一步,同时更新左边最大高度left_max。 b. 否则,右边可以接到水,计算当前位置能接的水量并加入volume,然后将右指针向中间移动一步,同时更新右边最大高度right_max。
- 返回水的容量volume。
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
// 初始化左指针left=0,
// 右指针right=n-1,
// 左边最大高度left_max=0,
// 右边最大高度right_max=0,
// 水的容量volume=0。
let n = height.length, left = 0, right = n - 1, left_max = 0, right_max = 0, volume = 0;
while (left <= right) {
// 如果left_max<right_max,则说明左边可以接到水,
// 计算当前位置能接的水量并加入volume,
// 然后将左指针向中间移动一步,
// 同时更新左边最大高度left_max。
if (left_max < right_max) {
// 更新左边最大高度left_max
left_max = Math.max(left_max, height[left]);
// 计算当前位置能接的水量
volume += Math.max(0, left_max - height[left]);
// 将左指针向中间移动一步
left++;
} else {
// 右边可以接到水,计算当前位置能接的水量并加入volume,
// 然后将右指针向中间移动一步,同时更新右边最大高度right_max。
// 更新右边最大高度right_max。
right_max = Math.max(right_max, height[right]);
// 计算当前位置能接的水量
volume += Math.max(0, right_max - height[right]);
// 将右指针向中间移动一步
right--;
}
}
// 返回水的容量
return volume;
}
代码执行结果如下:
上述解法时间复杂度为O(n),空间复杂度为O(1)。
如果你有其它解答思路,欢迎评论区留言讨论。
猜你喜欢
- 2024-11-22 【每日一题】数量刷题开始啦
- 2024-11-22 前端面试第二天
- 2024-11-22 前端面试总结
- 2024-11-22 「offerMe——刷题必备」java如何实现开根号的运算
- 2024-11-22 耗时7天我终于把LeetCode刷通关:数组十七连,真是不简单
- 2024-11-22 前端小姐姐的大厂面试过程复盘(微信/阿里/头条,附答案篇)
- 2024-11-22 刷 leetcode,进字节、阿里等一线大厂,刷题之前一定先打好基础
- 2024-11-22 作为前端开发者,你都经历过怎样的面试?
- 2024-11-22 被逼无奈学了几个mysql命令,竟然有大用
- 2024-11-22 刷题小程序怎么做?答题小程序开发制作流程
你 发表评论:
欢迎- 07-10Oracle 与 Google Cloud 携手大幅扩展多云服务
- 07-10分享收藏的 oracle 11.2.0.4各平台的下载地址
- 07-10Oracle 和 Microsoft 推出 Oracle Exadata 数据库服务
- 07-10Oracle Database@Azure 推进到南美等新区域并增加了新服务
- 07-10Oracle宣布推出 Oracle Database@AWS 的有限预览版
- 07-10Oracle与Nextcloud合作,推出主权云上的安全协作平台
- 07-10NodeRED魔改版连接MsSql、PostgreSQL、MySQL、OracleDB存储无忧
- 07-10对于企业数据云备份,“多备份”承诺的是成本更低,管理更高效#36氪开放日深圳站#
- 602℃几个Oracle空值处理函数 oracle处理null值的函数
- 594℃Oracle分析函数之Lag和Lead()使用
- 582℃0497-如何将Kerberos的CDH6.1从Oracle JDK 1.8迁移至OpenJDK 1.8
- 579℃Oracle数据库的单、多行函数 oracle执行多个sql语句
- 574℃Oracle 12c PDB迁移(一) oracle迁移到oceanbase
- 567℃【数据统计分析】详解Oracle分组函数之CUBE
- 554℃最佳实践 | 提效 47 倍,制造业生产 Oracle 迁移替换
- 548℃Oracle有哪些常见的函数? oracle中常用的函数
- 最近发表
-
- Oracle 与 Google Cloud 携手大幅扩展多云服务
- 分享收藏的 oracle 11.2.0.4各平台的下载地址
- Oracle 和 Microsoft 推出 Oracle Exadata 数据库服务
- Oracle Database@Azure 推进到南美等新区域并增加了新服务
- Oracle宣布推出 Oracle Database@AWS 的有限预览版
- Oracle与Nextcloud合作,推出主权云上的安全协作平台
- NodeRED魔改版连接MsSql、PostgreSQL、MySQL、OracleDB存储无忧
- 对于企业数据云备份,“多备份”承诺的是成本更低,管理更高效#36氪开放日深圳站#
- 解读丨《归档文件整理规则》— 电子文件元数据存储
- Data Guard跳归档恢复的实践(dataguard failover)
- 标签列表
-
- 前端设计模式 (75)
- 前端性能优化 (51)
- 前端模板 (66)
- 前端跨域 (52)
- 前端缓存 (63)
- 前端aes加密 (58)
- 前端脚手架 (56)
- 前端md5加密 (54)
- 前端路由 (61)
- 前端数组 (73)
- 前端js面试题 (50)
- 前端定时器 (59)
- 前端获取当前时间 (50)
- Oracle RAC (76)
- oracle恢复 (77)
- oracle 删除表 (52)
- oracle 用户名 (80)
- oracle 工具 (55)
- oracle 内存 (55)
- oracle 导出表 (62)
- oracle约束 (54)
- oracle 中文 (51)
- oracle链接 (54)
- oracle的函数 (57)
- 前端调试 (52)
本文暂时没有评论,来添加一个吧(●'◡'●)