42. 接雨水

题目介绍

给定 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

解答

C++解法

class Solution {
public:
    int trap(vector<int>& height) {
        // 双指针 前后最大值
        // 每个位置左边和右边最高高度分别记录在数组上
        // 每个位置可以储水的容量取决于其左右两边最大值之小者

        if(height.size() <= 2) return 0;
        vector<int> maxLeft(height.size(), 0);
        vector<int> maxRight(height.size(), 0);
        int size = maxRight.size();

        // 记录每个柱子左边的最大高度
        maxLeft[0] = height[0];
        for(int i = 1; i < size; ++i)
        {
            maxLeft[i] = max(maxLeft[i - 1], height[i]);
        }

        maxRight[size - 1] = height[size - 1];
        for(int i = size - 2; i >= 0; --i)
        {
            maxRight[i] = max(maxRight[i + 1], height[i]);
        }

        int res = 0;
        for(int i = 1; i < size; ++i)
        {
            res += min(maxRight[i], maxLeft[i]) - height[i];
        }
        return res;
    }
};

python3

class Solution:
    # 每一个位置能盛放多少水取决于其左边和右边柱子的最大高度的小者
    def trap(self, height: List[int]) -> int:
        n = len(height)
        # pre_max[i] 表示下标为i的柱子前面(包括下标为i的柱子)的最大高度
        pre_max = [0] * n
        pre_max[0] = height[0] 
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], height[i])

        # suf_max[i] 表示下标为i的柱子(包括下标为i的柱子)后面的最大高度
        suf_max = [0] * n
        suf_max[-1] = height[-1]
        #n-2 ~ 0 
        for i in range(n - 2, -1, -1):
            suf_max[i] = max(suf_max[i + 1], height[i])

        ans = 0
        # zip 将其中的列表打包成元组的列表用来迭代
        for h, pre, suf in zip(height, pre_max, suf_max):
            ans += min(pre, suf) - h

        return ans

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

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

相关文章

OpenShift 4 - 可观测性之用 OpenTelemetry+Jaeger 实现 Distributed Tracing

《OpenShift / RHEL / DevSecOps 汇总目录》 说明&#xff1a;本文已经在支持 OpenShift 4.13 的环境中验证 文章目录 技术架构部署 Distributed Tracing 运行环境安装测试应用并进行观测跟踪参考 说明&#xff1a; 本文使用的测试应用采用的是 “手动 Instrumentation” 方式在…

Linux系列---【CentOS 7通过MSTSC连接远程桌面】

安装对应的yum源 yum list lightdm xorgxrdp xrdp 可以看到这些软件都在epel中&#xff0c;如果没有的话&#xff0c;请先安装对应的yum源。命令如下&#xff1a; yum install -y epel-release 确认yum源没有问题之后&#xff0c;我们就可以进行安装了。 安装lightdm xorgxrdp…

【C语言】嵌入式C语言项目管理利器:深入理解Makefile的应用与实践

目录 一、makedile的概述 1、案例引入 2、makefile 3、Makefile优点 二、makefile的语法规则 1、语法规则 2、简单实战 三、makefile的变量 1、自定义变量 2、系统环境变量 3、预定义变量 4、高级makefile 一、makedile的概述 1、案例引入 gcc a.c b.c c.c ‐o …

EasyExcel写出包含多个sheet页的Excel

EasyExcel导出包含多个sheet页的Excel 1.引入依赖 引入如下的EasyExcel的依赖&#xff0c;或直接下载jar包 <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>3.1.1</version></depende…

RT-Thread快速入门-定时器管理

1时钟节拍 任何操作系统都需要提供一个时钟节拍&#xff0c;以供系统处理所有和时间有关的事件&#xff0c;如延时、线程的时间片轮转调度以及定时器超时等。时钟节拍&#xff08;OS Tick&#xff09;是操作系统中最小的时间单位。 时钟节拍是特定的周期性中断&#xff0c;这…

Spring Boot 整合 分布式搜索引擎 Elastic Search 实现 搜索、分页与结果过滤

文章目录 ⛄引言一、酒店搜索和分页⛅需求分析⚡源码编写 二、酒店结果过滤⌚需求分析⏰修改搜索业务 ✅效果图⛵小结 ⛄引言 本文参考黑马 分布式Elastic search Elasticsearch是一款非常强大的开源搜索引擎&#xff0c;具备非常多强大功能&#xff0c;可以帮助我们从海量数据…

【java实习评审】对热门小说更新时的聚集访问流量进行性能优化优化,有较好的设计

大家好&#xff0c;本篇文章分享一下【校招VIP】免费商业项目“推推”第一期书籍详情模块java同学的文档周最佳作品。该同学来自西安建筑科技大学软件工程专业。 本项目亮点难点&#xff1a;1 热门书籍在更新点的访问压力&#xff0c;2 书籍更新通知的及时性和有效性&#xff…

浅谈能源管理系统在水泥行业中设计分析

安科瑞 华楠 摘要&#xff1a;水泥企业作为我国产业结构中重要的耗能产业&#xff0c;同时对环境的污染也比较大&#xff0c;因此在水泥企业中建立能源管理系统&#xff0c;对水泥企业的生产过程过程进行全过程的监控和管理&#xff0c;对于降低企业的能源消耗和提高企业的经济…

24 鼠标常用事件

鼠标进入&#xff1a;enterEvent鼠标离开&#xff1a;leaveEvent鼠标按下&#xff1a;mousePressEvent鼠标释放&#xff1a;mouseRelaseEvent鼠标移动&#xff1a;mouseMoveEvent 提升为自定义控件MyLabel 代码&#xff1a; //mylabel.h #ifndef MYLABEL_H #define MYLABEL_H#…

ESP32(MicroPython) 两轮差速五自由度机械臂小车

这次的项目在软件上没多少调整&#xff0c;但本人希望分享一下硬件上的经验。 小车使用两轮差速底盘&#xff0c;驱动轮在小车中间&#xff0c;前后都要万向轮。这种形式可以实现0转弯半径&#xff0c;但受万向轮及用于加高的铜柱的规格限制&#xff0c;两个万向轮难以调到相同…

基于netlify生成custom SSL certificate

&#xff08;1&#xff09;腾讯云申请 &#xff08;2&#xff09;域名控制台解析 &#xff08;3&#xff09;Nginx下载&#xff08;crt: CA certificate Chain)

C++教程 从0开始

0基础C教程 从0开始 课堂现在开始 如需学习 请订阅该标签 什么是C&#xff1f; 这个不是太重要 自行查看该链接即可 C_百度百科C&#xff08;c plus plus&#xff09;是一种计算机高级程序设计语言&#xff0c;由C语言扩展升级而产生&#xff0c;最早于1979年由本贾尼斯特劳…

轻量级Firefox Send替代方案Gokapi

想不到一个域名的变动会影响这么大&#xff0c;访问量出现断崖式下跌。由此可见&#xff0c;平时的访问应该只是一些 RSS 的访问而已。 上面是 Pageviews&#xff0c;下面是 Uniques 今天略有回升 难怪那些大公司要花钱买域名了&#xff0c;不过老苏是个佛系的人&#xff0c;一…

使用MQ发送对象错误

说明&#xff1a;使用RabbitMQ发送消息&#xff0c;消息是对象&#xff0c;出现下面这样的错误&#xff1b; 错误信息&#xff1a;Caused by: com.fasterxml.jackson.databind.exc.InvalidDefinitionException: Cannot construct instance of com.hmall.item.pojo.Item (no Cr…

通过问题解决者手册推动你的结果 - 提高思维能力的 17 种方法

大部分人对产品管理的理解都是解决问题&#xff0c;这是他们的主要工作——找出客户的问题是什么并解决它们。但现在&#xff0c;热衷于解决问题的问题是&#xff0c;当我们看到问题时&#xff0c;本能反应是“我该如何解决它&#xff1f;” 这意味着&#xff1a;当我试图自己解…

SPEC CPU 2006 docker gcc:4 静态编译版本 Ubuntu 22.04 LTS 测试报错Invalid Run

runspec.sh #!/bin/bash source shrc ulimit -s unlimited runspec -c gcc41.cfg -T all -n 1 int fp > runspec.log 2>&1 & tail -f runspec.log runspec.log 由于指定了-T all&#xff0c;导致-n 1 失效&#xff0c;用例运行了三次&#xff08;后续验证&…

iptables的备份和还原

iptables的备份和还原 1、写在命令行当中的都是临时设置 2、把规则配置写在服务的文件当中&#xff0c;形成永久有效 备份&#xff1a;把iptables里面所有的配置都保存在/opt/ky30.bak中 iptables-save > /opt/ky30.bak 例&#xff1a; 默认配置文件在/etc/sysconfig/ip…

自然语言处理NLP介绍——NLP简介

目录 内容先进性说明内容大纲概要云服务器的使用 内容先进性说明 内容大纲概要 云服务器的使用

STM32MP157驱动开发——GPIO 和 和 Pinctrl 子系统的概念

文章目录 Pinctrl 子系统重要概念概述重要概念pin controller&#xff1a;client device&#xff1a; 代码中怎么引用 pinctrl GPIO 子系统重要概念概述在设备树中指定引脚在驱动代码中调用 GPIO 子系统头文件常用函数实例&#xff1a; BSP工程师针对芯片的寄存器写Pinctrl子系…

HTTPS安全套接字层超文本传输协议

HTTPS安全套接字层超文本传输协议 HTTPS简介HTTPS和HTTP的主要区别客户端在使用HTTPS方式与Web服务器通信时的步骤SSL/TLS协议的加密&#xff08;握手&#xff09;过程为什么数据传输阶段使用对称加密HTTPS 的优点HTTPS 的缺点HTTPS 的优化证书优化会话复用 HTTPS简介 HTTP协议…