【题解】42. 接雨水(动态规划 预处理)

https://leetcode.cn/problems/trapping-rain-water/description/
在这里插入图片描述

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        // 预处理数组
        vector<int> lefts(n, 0);
        vector<int> rights(n, 0);

        // 预处理记录左侧最大值
        lefts[0] = height[0];
        for (int i = 1; i < n; ++i) {
            lefts[i] = max(lefts[i-1], height[i]);
        }

        // 预处理记录右侧最大值
        rights[n-1] = height[n-1];
        for (int i = n - 2; i > 0; --i) {
            rights[i] = max(rights[i+1], height[i]);
        }

        // 将每个柱子可以接到水的值进行累加
        int ret = 0;
        for (int i = 0; i < n; ++i) 
        {
            if (min(lefts[i], rights[i]) - height[i] > 0)
                ret += min(lefts[i], rights[i]) - height[i];
        }    

        return ret;
    }
};

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

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

相关文章

Python应用 | 基于flask-restful+AntDesignVue实现的一套图书管理系统

本文将分享个人自主开发的一套图书管理系统&#xff0c;后端基于Python语言&#xff0c;采用flask-restful开发后端接口&#xff0c;前端采用VueAntDesignVue实现。对其他类似系统的实现&#xff0c;比如学生管理系统等也有一定的参考作用。有问题欢迎留言讨论~ 关注公众号&am…

最新Wireshark查看包中gzip内容

虽然是很简单的事情&#xff0c;但是网上查到的查看gzip内容的方法基本都是保存成zip文件&#xff0c;然后进行二进制处理。 其实现在最新版本的Wireshark已经支持获取gzip内容了。 选中HTTP协议&#xff0c;右键选择[追踪流]->[HTTP Stream] 在弹出窗口中&#xff0c;已…

mavsdk_server安卓平台编译

1.下载好mavsdk并进入mavsdk目录 2.生成docker安卓平台文件 docker run --rm dockcross/android-arm64 >./dockcross-android-arm64 3.生成makefile ./dockcross-android-arm64 cmake -DCMAKE_BUILD_TYPERelease -DBUILD_MAVSDK_SERVERON -DBUILD_SHARED_LIBSOFF -Bbuild/…

专业条码二维码扫描设备和手机二维码扫描软件的区别?

条码二维码技术已广泛应用于我们的日常生活中&#xff0c;从超市结账到公交出行&#xff0c;再到各类活动的入场验证&#xff0c;条码二维码的便捷性不言而喻&#xff0c;而在条码二维码的扫描识别读取过程中&#xff0c;专业扫描读取设备和手机二维码扫描软件成为了两大主要工…

【计算机毕业设计】003基于weixin小程序教学辅助

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

【Java】字符与字符串

1.字符char 字符数据类型用于表示单个字符。 字符数据类型char用于表示单个字符。字符型字面值用单引号括住。 char a A; char b 4; char c \u041; // A的Unicode字符串字面值必须括在双引号中。而字符字面值是括在单引号中的单个字符。因此"A"是一个字符串&…

视频号里的视频怎么下载保存?推荐5种方法!

很多人不知道视频号里的视频怎么下载保存&#xff0c;其实视频号下载提取方式比较多常见的有缓存、查看源代码、抓包、录屏、自动提取工具。 1&#xff1a;缓存 安卓手机特性将需要的视频观看完并缓存到手机&#xff0c;并将视频另外存为mp4文件&#xff0c;不过该方式最安卓1…

【扩散模型】【图像生成】FreeU:扩散 U-Net 模型的免费午餐(CVPR 2024 Oral))

论文名称&#xff1a;FreeU: Free Lunch in Diffusion U-Net (CVPR 2024 Oral) 论文地址&#xff1a;https//arxiv.org/pdf/2309.11497 项目链接&#xff1a;https//chenyangsi.top/FreeU/ 文章目录 摘要一、 扩散 U-Net 中的低频和高频分量二、扩散 U-Net 是如何执行去噪过程…

excel、word、ppt 下载安装步骤整理

请按照我的步骤开始操作&#xff0c;注意以下截图红框标记处&#xff08;往往都是需要点击的地方&#xff09; 第一步&#xff1a;下载 首先进入office下载网址&#xff1a; otp.landian.vip 然后点击下载 拉到下方 下载站点&#xff08;这里根据自己的需要选择下载&#x…

VLM技术介绍

1、背景 视觉语言模型&#xff08;Visual Language Models&#xff09;是可以同时从图像和文本中学习以处理许多任务的模型&#xff0c;从视觉问答到图像字幕。 视觉识别&#xff08;如图像分类、物体保护和语义分割&#xff09;是计算机视觉研究中一个长期存在的难题&#xff…

Excel第31享:基于left函数的截取式数据裂变

1、需求描述 如下图所示&#xff0c;在“Excel第30享”中统计2022年YTD各个人员的“上班工时&#xff08;a2&#xff09;”&#xff0c;需要基于工时明细表里的“日期”字段建立辅助列&#xff0c;生成“年份”字段&#xff0c;本文说明“年份”字段是怎么裂变而来的。 下图为…

前端web性能统计

前端web性能统计 1. 背景2. 业界方案2.1 腾讯2.2 蚂蚁金服2.3 字节跳动2.4 美团 3. 相关观念3.1 RAIL模型3.2 性能指标3.3 真实用户监控3.4 performance 4. 性能监控工具介绍5. 推荐采用方案 1. 背景 在如今的数字时代&#xff0c;网站和应用程序的性能对用户体验至关重要。用…

13_Shell系统函数

13_Shell系统函数和自定义函数 一、系统函数 basename 获取文件名 #!/bin/bash#basename 相对路径文件名 basename ./1.sh#basename 绝对路径文件名 basename /tmp/1.sh#basename 去除文件后缀名 basename /tmp/1.sh .shdirname 获取文件所在目录名 #!/bin/bash#dirname 相对路…

【web】-sql注入-login

根据网址提示打开如图&#xff1a; 查看源代码前台并没有过滤限制、扫描后台也没有发现特殊文件。看到标题显示flag is in database&#xff0c;尝试sql注入。 由于post,bp抓包如下&#xff1a; 运行python sqlmap.py -r 1.txt --dump 获取flag 42f4ebc342b6ed4af4aadc1ea75f…

在word中删除endnote参考文献之间的空行

如图&#xff0c;在References中&#xff0c;每个文献之间都有空行。不建议手动删除。打开Endnote。 打开style manager 删除layout中的换行符。保存&#xff0c;在word中更新参考文献即可。

【自学网络安全】二、防火墙NAT智能选路综合实验

任务要求&#xff1a; &#xff08;衔接上一个实验所以从第七点开始&#xff0c;但与上一个实验关系不大&#xff09; 7&#xff0c;办公区设备可以通过电信链路和移动链路上网(多对多的NAT&#xff0c;并且需要保留一个公网IP不能用来转换) 8&#xff0c;分公司设备可以通过总…

中小学校园EasyCVR视频综合监管方案:构建安全、智能的校园环境

一、背景需求分析 随着科技的快速发展&#xff0c;校园安全问题日益受到社会各界的关注。尤其是在中小学校园中&#xff0c;学生的安全更是牵动着每一个家庭的心。为了更有效地保障学生的安全&#xff0c;提高校园安全管理水平&#xff0c;视频监控系统在中小学中的应用越来越…

TikTok 入局小游戏,小游戏出海赛道大热,开发者如何抢滩海外市场?

国内小游戏市场的竞争日益激烈&#xff0c;开发成本上涨、买量的投入成本飙升&#xff0c;对小团队和个人开发者的资金要求量高。除此以外&#xff0c;单款游戏从软著、备案、到认证所需要的时间和费用都大幅提升&#xff0c;也对小游戏市场造成重大影响。重压之下&#xff0c;…

微信小程序如何实现登陆和注册功能?

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

算法day04 位运算 插入排序 二分法 对数器

位运算: 1&#xff09;有一个数组只包含这样的数&#xff0c;有几个数出现偶数次&#xff0c;有1个数出现奇数次&#xff0c;要求时间复杂度不超过o(n),怎么求出现奇数次的数。 使用 ^ 异或运算整个数组&#xff0c;偶数次运算结果为0&#xff0c;只留下最后一个奇数次的数。 …