面试经典-11-接雨水

题目

给定 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 个单位的雨水(蓝色部分表示雨水)。

class Solution {
    // 失败
    public int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            // 左右两边包括本个柱子的最大高度,在减去当前柱子高度,就是雨水的高度
            // 如果当前柱子太高的话也是存不住水的
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

为什么GPU对于人工智能如此重要?

GPU在人工智能中相当于稀土金属&#xff0c;甚至黄金&#xff0c;它们在当今生成式人工智能时代中的作用不可或缺。那么&#xff0c;为什么GPU在人工智能发展中如此重要呢&#xff1f; GPU概述 什么是GPU 图形处理器&#xff08;GPU&#xff09;是一种通常用于进行快速数学计…

基于YOLOv8深度学习的野外火焰烟雾检测系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战、目标检测

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

腾讯云轻量应用服务器地域选哪个合适?有啥区别?

腾讯云轻量应用服务器地域如何选择&#xff1f;地域就近选择&#xff0c;北方选北京地域、南方选广州地域&#xff0c;华东地区选上海地域。广州上海北京地域有什么区别&#xff1f;哪个好&#xff1f;区别就是城市地理位置不同&#xff0c;其他的差不多&#xff0c;不区分好坏…

【UE】制作系统设置功能

目录 效果 步骤 一、准备工作 二、创建画面设置界面 三、应用画面设置 四、保存画面设置 五、运动模糊与垂直同步 六、窗口化与分辨率 6.1 分辨率 6.2 窗口化 效果 步骤 一、准备工作 新建一个工程&#xff0c;创建游戏模式和玩家控制器&#xff0c;这里分别命名…

【代码随想录 | 数组 01】二分查找

文章目录 1.二分查找1.1题目1.2思路&#xff08;核心&#xff1a;区间的定义&#xff09;1.3左闭右闭1.4左闭右开1.5总结 1.二分查找 1.1题目 704.二分查找—力扣题目链接 题目&#xff1a;给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 …

centos7 yum 配置

centos7 yum 配置 重置yum更新 centos 镜像源http://mirrors.aliyun.com/centos/7Server/os/x86_64/repodata/repomd.xml: [Errno 14] HTTP Error 404 - Not Found 重置yum # 备份 sudo cp /etc/yum.repos.d/* /etc/yum.repos.d.bak/ # 删除 rm -rf /etc/yum.repos.d/*# 查看版…

【数据结构取经之路】快速排序及其优化

目录 简介 快速排序的实现步骤 快排的时间复杂度 快排的空间复杂度 霍尔法 证明 key > x left从key的位置出发的原因 霍尔法代码 (递归) 挖坑法 流程及其展开图 代码 (递归) 前后指针法 前后指针法的步骤及其动图 代码(递归) 快排的优化 一、三数取中 二、…

2024年泰迪智能科技合作伙伴战略大会暨产教融合实训基地落成仪式圆满结束

2024年泰迪智能科技合作伙伴战略大会 暨产教融合实训基地落成仪式 3月6日&#xff0c;2024年泰迪智能科技合作伙伴战略大会暨产教融合实训基地落成仪式在泰迪智能科技产教融合实训基地举行&#xff0c;本次合作伙伴战略大会围绕“龙腾山海&#xff0c;共赴新程 ”主题开展&…

【算法】链表手撕代码

目录 前言 1. 在原有的自定义链表类 Linked 的基础上&#xff0c;添加新的 “节点添加”方法 addNode(Node node) 测试用例 测试结果 2. 在自定义链表类的基础上&#xff0c;使用双重循环“强力” 判断两个节点是否发生相交 测试用例 测试结果 3. 在自定义链表类的基础…

运维自动化之——Ansible

目录 一、自动化运维 1、通过xshell实现自动化运维 2、Ansible简介 3、Ansible特点及优势 4、Ansible核心程序 5、Ansible工作原理及流程 6、部署Ansible自动化运维工具 7、Ansible常用模块 ①ansible命令模块 ②command模块 ③shell模块 ④cron模块 ⑤user模块 …

idea配置自定义注释模版和其他模板

项目场景&#xff1a; idea配置自定义模版 自定义注释模版其他模板&#xff0c;包括syso快捷键&#xff0c;swith快捷键等 自定义注释模版 1、File and Code Templates 第一种类创建完后头部自动生成注释模板 打开idea&#xff0c;选择 Settings--> Editor--> File a…

性能测试-数据库

一、数据库事务机制 ACID描述 1、原子性Atomicity&#xff1a;事务通常由多个语句组成。原子性保证将每个事务视为一个“单元”&#xff0c;该事务要么完全成功&#xff0c;要么完全失败 2、一致性Consistency&#xff1a;“一致”是指数据库中的数据是正确的&#xff0c;不存…

数据结构之单链表及其实现!

目录 ​编辑 1. 顺序表的问题及思考 2.链表的概念结构和分类 2.1 概念及结构 2.2 分类 3. 单链表的实现 3.1 新节点的创建 3.2 打印单链表 3.3 头插 3.4 头删 3.5 尾插 3.6 尾删 3.7 查找元素X 3.8 在pos位置修改 3.9 在任意位置之前插入 3.10 在任意位置删除…

深入解析CAS的原理机制

一、基本概述 1.1 引入背景 例&#xff1a;i。假设由线程A和B需要对i进行加1的操作。线程A和线程B会分别从主内存中读取i值到自己的工作内存中。原本相加之后的值为3&#xff0c;但线程A和线程B分别加1后将值刷新到主内存&#xff0c;发现主内存的值为2&#xff0c;出现错误。…

学c还行,学Python很累,还有其他语言适合我吗?

学c还行&#xff0c;学Python很累&#xff0c;还有其他语言适合我吗&#xff1f; 在开始前我分享下我的经历&#xff0c;我刚入行时遇到一个好公司和师父&#xff0c;给了我机会&#xff0c;一年时间从3k薪资涨到18k的&#xff0c; 我师父给了一些 电气工程师学习方法和资料&a…

新建项目module,但想归到一个目录下面

1. 想建几个module, 例如 component-base-service,component-config-service, 但是module多了会在CloudAction下面显示很多目录, 所以想把它们归到components模块下面去, 类似于下图的效果 2. 创建过程 右击CloudAction 新建 module -> 选maven类型 输入components, 建成后删…

【目标检测经典算法】R-CNN、Fast R-CNN和Faster R-CNN详解系列二:Fast R-CNN图文详解

RCNN算法详解&#xff1a;【目标检测经典算法】R-CNN、Fast R-CNN和Faster R-CNN详解系列一&#xff1a;R-CNN图文详解 学习视频&#xff1a;Faster RCNN理论合集 Fast RCNN 概念辨析 1. RoI 在Fast R-CNN中&#xff0c;RoI&#xff08;Region of Interest&#xff0c;感兴…

Spring多线程事务处理

一、背景 本文主要介绍了spring多线程事务的解决方案&#xff0c;心急的小伙伴可以跳过上面的理论介绍分析部分直接看最终解决方案。 在我们日常的业务活动中&#xff0c;经常会出现大规模的修改插入操作&#xff0c;比如在3.0的活动赛事创建&#xff0c;涉及到十几张表的插入…

使用DateUtil工具类偏移日期

使用DateUtil工具类偏移日期 一、依赖二、源码三、示例代码 一、依赖 <!--工具依赖--><dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.16</version></dependency>二、源码 …

Python常用图片数据方法

文章目录 1. 常用图片数据类型2. 图片的显示2.1 plt.imshow()2.2 使用 turtle 来绘制图片 3.图片ndarray数据的常用切片操作使用 cv2 来读取图片打印数据R G B 通道的获取BGR 转成 RGBcv2 不支持中文路径的解决方法 4 PIL.Image 转成 QImage 或 QPixmap 1. 常用图片数据类型 使…