Leetcode42题:接雨水

1.题目描述
给定 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

package com.iptv.prefecture.test;/*** @author: zhoumo* @descriptions: 接雨水*/
public class TrappingRainWater {public static void main(String[] args) {//  int[]  height = {0,1,0,2,1,0,1,3,2,1,2,1};int[]  height = {0,3,0,2,1,0,1,1,2,1,2,1};System.out.println(trap0(height));System.out.println(trap1(height));System.out.println(trap2(height));}// 暴力遍历解法public static int trap0(int[] height) {int n = height.length;if(n <= 1){return 0;}//定义两个数组,分别存储height[0,,,i]和height[i,,,n - 1]的最大值int[] leftMaxNum = new int[n];int[] rightMaxNum = new int[n];//初始化leftMaxNum[0] = height[0];rightMaxNum[n - 1] = height[n - 1];//计算i左侧的最大值for(int i = 1; i < n; i++){leftMaxNum[i] = Math.max(leftMaxNum[i - 1], height[i]);}for(int j = n - 2; j >= 0; j--){rightMaxNum[j] = Math.max(rightMaxNum[j + 1], height[j]);}//遍历计算每个位置能接住的雨水量int res = 0;for(int k = 1; k < n - 1; k++){res += Math.min(leftMaxNum[k], rightMaxNum[k]) - height[k];}return res;}//双指针static int trap2(int[] height) {// 总数int ans = 0;int left = 0;int right = height.length - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = Math.max(leftMax, height[left]);rightMax = Math.max(rightMax, height[right]);if (height[left] < height[right]) {ans += leftMax - height[left];++left;} else {ans += rightMax - height[right];--right;}}return ans;}}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Redis】 关于 Redis 哈希类型

文章目录 &#x1f343;前言&#x1f38b;命令介绍&#x1f6a9;hset&#x1f6a9;hget&#x1f6a9;hexists&#x1f6a9;hdel&#x1f6a9;hkeys&#x1f6a9;hvals&#x1f6a9;hgetall&#x1f6a9;hmget&#x1f6a9;hlen&#x1f6a9;hsetnx&#x1f6a9;hincrby&#x1…

SAP-CO成本控制概念之标准成本

“ 本篇介绍&#xff1a;标准成本的会计概念&#xff0c;标准成本的制定标准&#xff1b;通过结合会计标准成本的概念与SAP CO标准成本估算功能&#xff0c;更具象化的了解SAP如何实现标准成本管理&#xff0c;为后续学习SAP实际成本核算打下基础。” 01 — 背景需求 SAP实施…

最重要的时间表示,柯桥外贸俄语小班课

в第四格 1、与表示“钟点”的数词词组连用 例&#xff1a; в шесть часов утра 在早上六点 в пять тридцать 在五点半 2、与表示“星期”的名词连用 例&#xff1a; в пятницу 在周五 в следующий понедельник …

LeetCode 第399场周赛个人题解

100323. 优质数对的总数 I 原题链接 100323. 优质数对的总数 I 思路分析 签到题 AC代码 class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:n, m len(nums1), len(nums2)ret 0for i in range(n):for j in range(m):if nu…

千亿级开源大模型Qwen110B部署实测

近日&#xff0c;通义千问团队震撼开源 Qwen1.5 系列首个千亿参数模型 Qwen1.5-110B-Chat。 千亿级大模型普通显卡是跑不了推理的&#xff0c;普通人一般也没办法本地运行千亿级大模型。 为了探索千亿级大模型到底需要计算资源&#xff0c;我用云计算资源部署了Qwen1.5-110B-…

Leetcode 剑指 Offer II 079.子集

题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer&#xff08;专项突击版&#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 给定一个整数数组 nums &#xff0c;数组中的元素 互不相同 。返…

20232801 2023-2024-2 《网络攻防实践》实践十一报告

#20232801 2023-2024-2 《网络攻防实践》实践十一报告 1.实践内容 &#xff08;1&#xff09;web浏览器渗透攻击 使用攻击机和Windows靶机进行浏览器渗透攻击实验&#xff0c;体验网页木马构造及实施浏览器攻击的实际过程。 &#xff08;2&#xff09;取证分析实践—网页木马…

北核论文完美复现:自适应t分布与动态边界策略改进的算术优化算法

声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 原始算术优化算法 改进点1&#xff1a;引入…

那智不二越机器人维修案例分享

那智不二越工业机器人在工业范围内广泛应用于各种生产领域。其示教器作为人机交互的重要设备&#xff0c;常常需要定期维护和Nachi不二越机械手示教盒修理。 【Nachi不二越机器人示教器维修步骤】 1. 关闭电源 在进行任何那智不二越机器人维修操作之前&#xff0c;务必确保机器…

IDEA打开项目报错

IDEA打开项目报错&#xff1a; Cannot read scheme C:\Users\xxxxxx\AppData\Roaming\JetBrains\IntelliJIdea2023.2\qaplug_profiles\Default.xmljava.lang.AbstractMethodError: Receiver class com.soldevelo.qaplug.scanner.AnalysisProfileManager$2 does not define or i…

单条16g和双条8g哪个好

单条16g和双条8g各有优劣,具体选择要根据个人需求和电脑配置来决定。 以下是一些参考信息: •单条16g内存的价格比双条8g内存的价格低,而且16g的内存容量大,一条内存十分的方便。 •两条8g内存可以组成双通道,电脑运行速度要快一些。 •对于普通使用电脑的人群与热衷于…

项目管理-人力资源管理

目录 一、概述 二、人力资源计划编制 2.1 概述 2.2 层次结构图 2.3 分配任务矩阵 三、组建项目团队 3.1 概述 3.2 内部谈判 3.3 事先分派 3.4 外部招聘 3.5 虚拟团队 3.6 总结 四、项目团队建设 4.1 概述 4.2 团队发展过程 4.2.1 概述 4.2.2 形成期 4.2.3 震…

vue3 ts问题 找不到模块“@/views/home/index.vue”或其相应的类型声明。

1. 找不到模块“/views/HomeView.vue”或其相应的类型声明 今天帮同事看了一个问题&#xff0c;他尝试用vitevue3tspinia创建项目&#xff0c;结果刚上来就遇到这么一个问题 2. 解决办法 出现这个问题的原因就是&#xff1a;ts只支持导出导入模块&#xff0c;但是vue不是模块…

红蓝对抗-HW红蓝队基本知识(网络安全学习路线笔记)

第一, 什么是蓝队 蓝队&#xff0c;一般是指网络实战攻防演习中的攻击一方。 蓝队一般会采用针对目标单位的从业人员&#xff0c;以及目标系统所在网络内的软件、硬件设备同时执行多角度、全方位、对抗性的混合式模拟攻击手段&#xff1b;通过技术手段实现系统提权、控制业务、…

利用Python去除PDF水印

摘要 本文介绍了如何使用 Python 中的 PyMuPDF 和 OpenCV 库来从 PDF 文件中移除水印&#xff0c;并将每个页面保存为图像文件的方法。我们将深入探讨代码背后的工作原理&#xff0c;并提供一个简单的使用示例。 导言 简介&#xff1a;水印在许多 PDF 文件中都很常见&#x…

自建公式,VBA在Excel中轻松获取反义词

自建公式&#xff0c;VBA在Excel中轻松获取反义词 文章目录 前言一、爬取网站数据二、代码1.创建数据发送及返回方法2.汉字转UTF8编码2.获取反义词 三、运行效果截图 前言 小学语文中&#xff0c;近义词、反义词是必考内容之一。家长不能随时辅导怎么办&#xff1f;有VBA&…

脚注:书籍的小秘密,躲藏在脚注间

脚注&#xff1a;书籍的小秘密&#xff0c;躲藏在脚注间 脚注是一种在文本中提供补充信息、引用出处或注解的方式&#xff0c;有助于读者更全面地理解文中内容&#xff0c;并为进一步研究提供参考和跳转点。 在一书本中&#xff0c;脚注是额外提供给读者的文字信息&#xff0…

自动化您的任务——crewAI 初学者教程

今天&#xff0c;我写这篇文章是为了分享您开始使用一个非常流行的多智能体框架所需了解的所有信息&#xff1a;crewAI。 我将在这里或那里跳过一些内容&#xff0c;使本教程成为一个精炼的教程&#xff0c;概述帮助您入门的关键概念和要点 今天&#xff0c;我写这篇文章是为了…

RedHat9 | DNS剖析-配置主DNS服务器实例

一、实验环境 1、BIND软件包介绍 BIND软件是一款开放源码的DNS服务器软件&#xff0c;由美国加州大学Berkeley分校开发和维护&#xff0c;全称为Berkeley Internet Name Domain。该软件在DNS&#xff08;域名系统&#xff09;领域具有重要地位&#xff0c;是目前世界上使用最…