【算法速刷(9/100)】LeetCode —— 42.接雨水

目录

自我解法

官方解法

解法一:动态规划、前后缀

解法二:单调栈

自我解法

这道题刚拿到的时候,第一时间的想法是将其想象成MC一样的方块世界,如何去生成水一样的去解决。后来发现有点复杂化了,因为题目只需要累计的结果数字,不需要额外的东西,但因为先入为主的观念,我还是选择了从低到高从左到右依次遍历的模拟法,这种方法的复杂度基本上是O(N * MaxHeight),实际也是十分低效,但私以为思路也是值得一分享,最后用例通过319/323。

class Solution {
public:int trap(vector<int>& height) {//从低到高从右向左打射线,找到间隔布置的两个方块,计算间隔,累加到结果上int res = 0;int n = height.size();int maxHeight = *max_element(height.begin(), height.end());for(int y = 1; y <= maxHeight; y++){int lastBlockX = -1;for(int x = 0; x < n; x++){if(height[x] >= y){if(lastBlockX != -1){res += x - lastBlockX - 1;}lastBlockX = x;}}}return res;}
};

官方解法

官方的解法从数学角度考虑,并没有被这张图迷倒,而是在一维上解决问题,从这个角度出发,怎么也不会搞出来O(n * MaxHeight)的复杂度。

解法一:动态规划、前后缀

正所谓问题的关键在于找到关键的问题,这道题的关键也就是关键的问题:如何在数组的某个位置上计算其位置上能积累的水的高度?

实际上给定位置上能积水的高度就是“左边最高高度和右边最高高度”中的最小值。

我们可以通过构造两个数组来分别记录一个位置上左边和右边的最高高度,O(2N)的复杂度即可完成构造。注意构造的数组的值,不应低于当前位置的高度,假设左边高度始终低于当前高度,则在数组中记录为当前位置的高度,这样可以保证构造的数组减去原数组中当前位置高度不会出现负值。

最后指定一个位置,其能积累的水高度就是 min(leftMaxH, rightMaxH) - currentH

这个算式的值域 >= 0

最后时间复杂度即为O(3n) = O(n),漂亮滴很呐

class Solution {
public:int trap(vector<int>& height) {//预处理每个方块的左边和右边的最大数//该区块的纵向存水数量为左右墙中最低的高度减去自身int n = height.size();vector<int> leftMax(n);leftMax[0] = height[0];for(int i = 1; i < n; i++)leftMax[i] = max(leftMax[i - 1], height[i]);vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for(int i = n - 2; i >= 0; i--)rightMax[i] = max(rightMax[i + 1], height[i]);int res = 0;for(int i = 0; i < n; i++)res += min(leftMax[i], rightMax[i]) - height[i];return res;}
};

解法二:单调栈

除了上面比较常见的做法,还有就是使用单调栈。直观来说,通过维护一个单调递减的栈,可以通过进栈出栈来识别哪里是洼地,进栈则坡的方向是↘,出栈则坡的方向是↗。遇到递增则进行出栈操作,两个坐标之间的间隔必为空,即可以储水,累加到结果中。

需要注意的是,在出栈的操作中,需要三个高度

  • 第一个高度(栈顶),代表需要忽略的高度,因为是上一次已经处理过的,不忽略会导致重复累加
  • 第二个高度(次栈顶),代表当前蓄水的左边界高度,本次循环中不出栈,等下一次出栈。
  • 第三个高度(当前遍历到的),代表当前蓄水的右边界高度,尚未入栈。

如果是第一次做的话,还是很难想到这样写的,Debug会疯掉哒

class Solution {
public:int trap(vector<int>& height) {stack<int> stk;int n = height.size();int res = 0;for(int i = 0; i < n; i++){while(!stk.empty() && height[i] > height[stk.top()]){int top = stk.top();stk.pop();if(stk.empty())break;int left = stk.top();int space = i - left - 1;int h = min(height[left], height[i]) - height[top];res += space * h;}stk.push(i);}return res;}
};

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

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

相关文章

Spring学习笔记(四)

二十一、Spring事务详解 &#xff08;一&#xff09;、Spring基于XML的事务配置 1.环境搭建 1.1 构建maven工程&#xff0c;添加相关技术依赖 <dependencies><dependency><groupId>org.springframework</groupId><artifactId>spring-context…

区块链技术在知识产权保护中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 区块链技术在知识产权保护中的应用 区块链技术在知识产权保护中的应用 区块链技术在知识产权保护中的应用 引言 区块链技术概述 …

NLP论文速读(NeurIPS2024)|使用视觉增强的提示来增强视觉推理

论文速读|Enhancing LLM Reasoning via Vision-Augmented Prompting 论文信息&#xff1a; 简介: 这篇论文试图解决的问题是大型语言模型&#xff08;LLMs&#xff09;在处理包含视觉和空间线索的推理问题时的局限性。尽管基于LLMs的推理框架&#xff08;如Chain-of-Thought及其…

Qt_day7_文件IO

目录 文件IO 1. QFileDialog 文件对话框&#xff08;熟悉&#xff09; 2. QFileInfo 文件信息类&#xff08;熟悉&#xff09; 3. QFile 文件读写类&#xff08;掌握&#xff09; 4. UI操作与耗时操作&#xff08;掌握&#xff09; 5. 多线程&#xff08;掌握&#xff09;…

如何管理好自己的LabVIEW项目

在LabVIEW项目开发中&#xff0c;项目管理对于提高开发效率、确保项目质量、减少错误和维护成本至关重要。以下从项目规划、代码管理、测试与调试、版本控制、团队协作等方面&#xff0c;分享LabVIEW项目管理的体会。 ​ 1. 项目规划与需求分析 关键步骤&#xff1a; 需求分析…

三周精通FastAPI:40 部署应用程序或任何类型的 Web API 概念

官方文档&#xff1a;部署概念 - FastAPI 部署概念 在部署 FastAPI 应用程序或任何类型的 Web API 时&#xff0c;有几个概念值得了解&#xff0c;通过掌握这些概念您可以找到最合适的方法来部署您的应用程序。 一些重要的概念是&#xff1a; 安全性 - HTTPS启动时运行重新…

【算法一周目】双指针(1)

目录 1.双指针介绍 2.移动零 解题思路 C代码实现 3.复写零 解题思路 C代码实现 4.快乐数 解题思路 C代码实现 5.盛水最多的容器 解题思路 C代码实现 1.双指针介绍 常见的双指针有两种形式&#xff0c;一种是对撞指针&#xff0c;一种是快慢指针。 对撞指针&#x…

ARXML汽车可扩展标记性语言规范讲解

ARXML: Automotive Extensible Markup Language &#xff08;汽车可扩展标记语言&#xff09; xmlns: Xml name space &#xff08;xml 命名空间&#xff09; xsd: Xml Schema Definition (xml 架构定义) 1、XML与HTML的区别&#xff0c;可扩展。 可扩展&#xff0c;主要是…

自监督学习:机器学习的未来新方向

引言 自监督学习&#xff08;Self-Supervised Learning, SSL&#xff09;是近年来机器学习领域的一个重要发展方向&#xff0c;迅速成为许多研究和应用的热点。与传统的监督学习不同&#xff0c;自监督学习利用未标注数据&#xff0c;通过设计自我生成标签的任务&#xff0c;帮…

FFMPEG录屏(22)--- Linux 下基于X11枚举所有显示屏,并获取大小和截图等信息

众人拾柴火焰高&#xff0c;github给个star行不行&#xff1f; open-traa/traa traa is a versatile project aimed at recording anything, anywhere. The primary focus is to provide robust solutions for various recording scenarios, making it a highly adaptable tool…

多媒体信息检索

文章目录 一、绪论二、文本检索 (Text Retrieval)(一) 索引1.倒排索引2.TF-IDF (二) 信息检索模型 (IR模型&#xff0c;Information Retrieval)1.布尔模型 (Boolean模型)(1)扩展的布尔模型 (两个词)(2)P-Norm模型 (多个词) 2.向量空间模型 (Vector Space Model&#xff0c;VSM)…

MySql-8.0.40安装详细教程

文章目录 原创下载安装包安装配置初始化MySQL数据库安装mysql服务并启动启动MySQL服务连接MySQL配置环境变量 原创 MySql-8.0.26安装详细教程&#xff08;保姆级&#xff09; 下载安装包 MySQL Community Downloads 直接到选择MySQL Community Server版本页面 MySQL Commun…

openai Realtime API (实时语音)

https://openai.com/index/introducing-the-realtime-api/ 官方demo https://github.com/openai/openai-realtime-console 官方demo使用到的插件 https://github.com/openai/openai-realtime-api-beta?tabreadme-ov-file 装包配置 修改yarn.lock 这个包是从github下载的 &q…

杨辉三角-一维数组与二维数组解法

这种问题是很有规律的 这里 总结一下 这类问题输出&#xff1a;对称 且数据相同的很多 就比如首位都是1 如果计算中间值遇到困难 可以试着把边界值单独输出 一维数组 // // Created by 徐昌真 on 2024/11/11. // #include <stdio.h> //一维数组 int main() {int n; /…

无人机反制技术与方法:主动防御,被动防御技术原理详解

无人机反制技术与方法主要分为主动防御和被动防御两大类&#xff0c;以下是关于这两类防御技术的原理详解&#xff1a; 主动防御技术原理 主动防御系统旨在通过直接干扰或摧毁来攻击入侵的无人机。这类系统通常包括电子干扰、激光武器、定向能武器以及硬杀伤手段&#xff08;如…

计算机毕业设计Python+图神经网络考研院校推荐系统 考研分数线预测 考研推荐系统 考研爬虫 考研大数据 Hadoop 大数据毕设 机器学习 深度学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

小白初入Android_studio所遇到的坑以及怎么解决

1. 安装Android_studio 参考&#xff1a;Android Studio 安装配置教程 - Windows(详细版)-CSDN博客 Android Studio超级详细讲解下载、安装配置教程&#xff08;建议收藏&#xff09;_androidstudio-CSDN博客 想下旧版本的android_studio的地址&#xff08;仅供参考&#xf…

020_Servlet_Mysql学生选课系统(新版)_lwplus87

摘 要 随着在校大学生人数的不断增加&#xff0c;教务系统的数据量也不断的上涨。针对学生选课这一环节&#xff0c;本系统从学生网上自主选课以及课程发布两个大方面进行了设计&#xff0c;基本实现了学生的在线信息查询、选课功能以及教师对课程信息发布的管理等功能&…

Vue Cli 脚手架目录文件介绍

小试牛刀 //vetur高亮; vuetab 快速生成 <template><div class"box">我是个盒子<button click"fn">按钮</button></div> </template><script> export default {methods:{fn(){alert("Hello Vue")}} …

[安洵杯 2019]easy_web 详细题解

知识点: 编码转换 命令执行 linux空格_关键字绕过 打开页面 发现url 是 /index.php?imgTXpVek5UTTFNbVUzTURabE5qYz0&cmd 有img参数和cmd参数 cmd参数是没赋值的,随便赋值为123456 页面没有反应 鼠标移动到图片下面时发现有东西,当然直接查看页面源代码也可以发现 尝…