leetcode算法题之接雨水

这是一道很经典的题目,问题如下:

题目地址

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

解法1:动态规划

动态规划的核心就是将问题拆分成若干个子问题求解,那这道题的问题实际上可以拆分为求x轴上每一块区域能承载多少雨水,而x轴上每一块区域能承载多少雨水取决于它左边和右边的最大高度值以及它的自身高度,所以我们可以先维护两个数组leftMaxArr和rightMaxArr

// height是leetcode传进来的高度数组leftMaxArr[i] = Math.max(leftMaxArr[i - 1], height)
rightMaxArr[i] = Math.min(rightMaxArr[i + 1], height)

leftMaxArr每一项对应着从左到当前区域高度的最大值,rightMaxArr就是从右到当前区域

知道了x轴上每一块区域的左右高度最大值后那这个子问题就很简单了,我们先定义一个子问题的结果数组result,那么公式可以这么写

result[i] = Math.max(leftMaxArr, rightMaxArr) - height[i]

最后将这个result数组的值加起来,就是本道题的结果了,当然,我们不需要使用到result数组,用一个变量维护即可,代码如下

/*** @param {number[]} height* @return {number}*/
var trap = function(height) {const len = height.lengthconst leftMaxArr = [], rightMaxArr = []let result = 0leftMaxArr[0] = height[0]rightMaxArr[len - 1] = height[len - 1]for (let i = 1; i < len - 1; i++) {leftMaxArr[i] = Math.max(leftMaxArr[i - 1], height[i])}for (let i = len - 2; i > 0; i--) {rightMaxArr[i] = Math.max(rightMaxArr[i + 1], height[i])}// 忽略 0 和 len - 1,因为它们是边界,不会有雨水for (let i = 1; i < len - 1; i++) {result += Math.min(leftMaxArr[i], rightMaxArr[i]) - height[i]}return result
};

解法2:双指针

这个解法是由解法一衍生而来,由解法一发现我们不需要同时知道左右的最大高度,只需要知道高度比较小的一侧,所以我们可以定义两个指针往中间收缩,每一次收缩的位置即为高度较小的一侧,这样就不用维护两个数组了,空间复杂度为O(1),代码如下:

/*** @param {number[]} height* @return {number}*/
var trap = function(height) {const len = height.lengthlet leftMax = height[0], rightMax = height[len - 1]let result = 0let left = 0, right = len - 1while (left < right) {// 此时leftMax一定小于rightMax,好比打擂台,强大的人可以一直打下去~if (height[left] < height[right]) {// 左侧为高度较小的一侧,对左指针当前位置用左侧最大高度进行计算result += leftMax - height[left]left++// 更新左侧最大高度leftMax = Math.max(leftMax, height[left])} else {result += rightMax - height[right]right--rightMax = Math.max(rightMax, height[right])}}return result
}

这样这个问题就完美解决啦,leetcode还有一种关于单调栈的解法,有兴趣的可以了解下~

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

2024算法、高性能计算与人工智能国际学术会议(AHPCAI 2024)

2024算法、高性能计算与人工智能国际学术会议&#xff08;AHPCAI 2024&#xff09; 2024 International Conference on Algorithms, High Performance Computing and Artificial Intelligence 2024年8月14-16日 | 中国-郑州 2024中国算力大会正在发起“算力中国最佳学术论文…

今天我们聊聊C#的并发和并行

并发和并行是现代编程中的两个重要概念&#xff0c;它们可以帮助开发人员创建高效、响应迅速、高性能的应用程序。在C#中&#xff0c;这些概念尤为重要&#xff0c;因为该语言提供了对多线程和异步编程的强大支持。本文将介绍C#中并发和并行编程的关键概念、优点&#xff0c;并…

Langchain核心模块与实战[7]:专业级Prompt工程调教LLM[输入输出接口、提示词模板与例子选择器的协同工程]

Langchain核心模块与实战[7]:专业级Prompt工程调教LLM[输入输出接口、提示词模板与例子选择器的协同工程] 1. 大模型IO接口 任何语言模型应用的核心元素是…模型的输入和输出。LangChain提供了与任何语言模型进行接口交互的基本组件。 提示 prompts : 将模型输入模板化、动态…

【LeetCode:3096. 得到更多分数的最少关卡数目+ 前缀和】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

百度,有道,谷歌翻译API

API翻译 百度&#xff0c;有道&#xff0c;谷歌API翻译&#xff08;只针对中英相互翻译&#xff09;,其他语言翻译需要对应from&#xff0c;to的code 百度翻译 package fills.tools.translate; import java.util.ArrayList; import java.util.HashMap; import java.util.Lis…

宠物空气净化器哪款除臭效果好?质量好的养狗空气净化器排名

作为一个宠物家电小博主&#xff0c;炎炎夏日&#xff0c;家中的宠物给你带来的不仅仅是温暖的陪伴&#xff0c;还有那挥之不去的宠物异味。普通空气净化器虽然能够应对一般的空气净化需求&#xff0c;但对于养猫家庭特有的挑战&#xff0c;如宠物毛发、皮屑和异味等&#xff0…

大模型微调部署实战及类GPT工具的高效使用

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于大模型算法的研究与应用。曾担任百度千帆大模型比赛、BPAA算法大赛评委,编写微软OpenAI考试认证指导手册。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。授权多项发明专利。对机器学…

CSS3雷达扫描效果

CSS3雷达扫描效果https://www.bootstrapmb.com/item/14840 要创建一个CSS3的雷达扫描效果&#xff0c;我们可以使用CSS的动画&#xff08;keyframes&#xff09;和transform属性。以下是一个简单的示例&#xff0c;展示了如何创建一个类似雷达扫描的动画效果&#xff1a; HTM…

libtins初探-抓包嗅探

libtin 一、概述1. 可移植性2. 特性 二、基础知识1. PDU2. 地址类3. 地址范围类4. 网络接口5. 写pcap文件 三、嗅探1.嗅探基础2. 嗅探器配置3. 循环嗅探4. 使用迭代器嗅探6. 包对象7. 读取pcap文件8. 包的解析 四、发送包1. 发送网络层pdu2. 发送链路层pdu3. 发送和接收响应校验…

自训练和增量训练word2vec模型

1、自己准备训练语料文件 根据自己的业务场景准备训练数据&#xff0c;比如用户在商城上的同购行为序列或同浏览行为序列。 我们希望通过自己训练业务相关的语料word2vec模型来获得词嵌入、词相关性查询等。 1.1 准备语料库文件 # 示例&#xff1a;准备自己的一个大规模的语…

开局一个启动器:从零开始入坑ComfyUI

前几天刷某乎的时候看到了一位大佬写的好文&#xff0c;可图 IP-Adapter 模型已开源&#xff0c;更多玩法&#xff0c;更强生态&#xff01; - 知乎 (zhihu.com) 久闻ComfyUI大名&#xff0c;决定试一下。这次打算不走寻常路&#xff0c;不下载现成的一键包了&#xff0c;而是…

7.23模拟赛总结 [数据结构优化dp] + [神奇建图]

目录 复盘题解T2T4 复盘 浅复盘下吧… 7:40 开题 看 T1 &#xff0c;起初以为和以前某道题有点像&#xff0c;子序列划分&#xff0c;注意到状态数很少&#xff0c;搜出来所有状态然后 dp&#xff0c;然后发现这个 T1 和那个毛关系没有 浏览了一下&#xff0c;感觉 T2 题面…

宠物经济纵深观察:口红效应显著,呈可持续发展态势

七月以来&#xff0c;全国各地陆续开启高温模式。和人一样&#xff0c;“毛孩子们”同样也难耐高温&#xff0c;由此&#xff0c;围绕猫猫狗狗的“宠物经济”迅速升温&#xff0c;宠物冰垫、宠物饮水机、宠物烘干机......一系列宠物单品掀起夏日消费热潮。 就在几天前&#xf…

Hbase映射为Hive外表

作者&#xff1a;振鹭 Hbase对应Hive外表 (背景&#xff1a;在做数据ETL中&#xff0c;可能原始数据在列式存储Hbase中&#xff0c;这个时候&#xff0c;如果我们想清洗数据&#xff0c;可以考虑把Hbase表映射为Hive的外表&#xff0c;然后使用Hive的HQL来清除处理数据) 1. …

Java面试八股之Spring boot的自动配置原理

Spring boot的自动配置原理 Spring Boot 的自动配置原理是其最吸引人的特性之一&#xff0c;它大大简化了基于 Spring 框架的应用程序开发。以下是 Spring Boot 自动配置的基本原理和工作流程&#xff1a; 1. 启动类上的注解 Spring Boot 应用通常会在主类上使用 SpringBoot…

真实测评,霍尼韦尔、希喂、352宠物空气净化器性能对比

在快节奏的社会生活中&#xff0c;人们越来越注重精神需要&#xff0c;许多年轻人纷纷选择拥抱宠物&#xff0c;作为生活中的温馨伴侣。宠物们治愈心灵的同时也要付出一定“代价”&#xff0c;日常养护&#xff0c;如清理猫毛、管理气味以及保持宠物环境的清洁&#xff0c;都是…

webpack的基本介绍与使用

webpack基本介绍及其基础案例 概念 Webpack 是一个现代 JavaScript 应用程序的静态模块打包器&#xff08;module bundler&#xff09;。当 webpack 处理应用程序时&#xff0c;它会递归地构建一个依赖关系图&#xff0c;其中包含应用程序需要的每个模块&#xff0c;然后将所…

学习记录day16—— 数据结构 双向链表 循环链表

双向链表 1、概念 1&#xff09;就是从任意一个节点既能存储其前驱节点&#xff0c;又能存储后继节点 2)结构体中增加一个指向前驱节点的指针 //定义数据类型 typedef int datatype;//定义节点类型 typedef struct Node {union {int len;datatype data;};struct Node *prio; …

72 | 数据分析岗位招聘数据可视化

项目介绍 本项目旨在通过对智联招聘网站上发布的数据分析岗位信息的分析和可视化,帮助应届毕业生和希望进入数据分析行业的专业人士更好地理解当前的就业市场。通过收集包含职位名称、薪资范围、地点、工作经验、学历要求等关键信息的数据,项目深入探讨了数据分析岗位的多个…

【大师与bug里特】M_Studio《王国之梦》学习笔记

1️⃣ Object & object(✅) 之辨 《7.泛型事件框架〈余2min左右时〉》 不然inspector窗口的最后一行&#xff08;告诉我们订阅者是SceneLoadManager它身上挂了☝️ObjectEventListener用来监听这个事件 有多少个事件注册到这里来了都能够看到&#xff09;还是不会出现 加上…