当前位置: 首页 > news >正文

【别再困扰于LeetCode接雨水问题了 | 从暴力法=>动态规划=>单调栈】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ 暴力法
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 动态规划
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 单调栈
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 🍋 总结
    • 💬 共勉

🚩 题目链接

  • 42. 接雨水

⛲ 题目描述

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

img
输入: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

🌟 求解思路&实现代码&运行结果


⚡ 暴力法

🥦 求解思路

暴力法的思路很简单,对于每一个柱子,我们找到其左右两侧的最大高度,分别记为 l e f t M a x leftMax leftMax r i g h t M a x rightMax rightMax,然后计算其储水量 m i n ( l e f t M a x , r i g h t M a x ) − h e i g h t i min(leftMax, rightMax) - height_i min(leftMax,rightMax)heighti,将所有储水量累加起来即可。

🥦 实现代码

class Solution {public int trap(int[] height) {int n = height.length;int ans = 0;for (int i = 0; i < n; i++) {int leftMax = 0;int rightMax = 0;for (int j = i; j >= 0; j--) leftMax = Math.max(leftMax, height[j]);for (int j = i; j < n; j++) rightMax = Math.max(rightMax, height[j]);ans += Math.min(leftMax, rightMax) - height[i];}return ans;}
}

🥦 运行结果

时间复杂度为 O ( n 2 ) O(n^2) O(n2)

在这里插入图片描述


⚡ 动态规划

🥦 求解思路

我们可以使用动态规划来优化暴力法。首先预处理出每个位置左侧的最大高度和右侧的最大高度,分别存储在数组 l e f t M a x leftMax leftMax r i g h t M a x rightMax rightMax 中。然后对于每个位置,计算其储水量 m i n ( l e f t M a x [ i ] , r i g h t M a x [ i ] ) − h e i g h t [ i ] min(leftMax[i], rightMax[i]) - height[i] min(leftMax[i],rightMax[i])height[i],将所有储水量累加起来即可。

🥦 实现代码

class Solution {public int trap(int[] height) {int n=height.length;int[] leftMax=new int[n];int[] rightMax=new int[n];leftMax[0]=height[0];rightMax[n-1]=height[n-1];for(int i=1;i<n;i++) leftMax[i]=Math.max(leftMax[i-1],height[i]);for(int i=n-2;i>=0;i--) rightMax[i]=Math.max(rightMax[i+1],height[i]);int ans=0;for(int i=0;i<n;i++) ans+=Math.min(leftMax[i],rightMax[i])-height[i];return ans;}
}

🥦 运行结果

时间复杂度为 O ( n ) O(n) O(n)

在这里插入图片描述


⚡ 单调栈

🥦 求解思路

使用单调栈来优化动态规划。我们使用栈来维护一个递减的柱子高度序列。具体地,遍历到第 i i i 个柱子时,如果当前柱子的高度 h e i g h t [ i ] height[i] height[i] 小于栈顶柱子的高度,则将当前柱子入栈;否则,不断从栈中弹出元素,直到栈为空或者当前栈顶元素的高度大于 h e i g h t [ i ] height[i] height[i],然后将当前柱子入栈。弹出元素时,我们可以计算其储水量,并将其累加到答案中。

🥦 实现代码

class Solution {public int trap(int[] height) {int n = height.length;Stack<Integer> stack = new Stack<>();int ans = 0;for (int i = 0; i < n; i++) {while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int top = stack.pop();if (stack.isEmpty()) {break;}int left = stack.peek();int width = i - left - 1;int heightDiff = Math.min(height[left], height[i]) - height[top];ans += width * heightDiff;}stack.push(i);}return ans;}
}

🥦 运行结果

时间复杂度为 O ( n ) O(n) O(n)

在这里插入图片描述


🍋 总结

本文介绍了三种解法来解决 LeetCode 42 题,即接雨水问题。暴力法时间复杂度较高,使用动态规划和单调栈可以优化其效率。动态规划和单调栈的时间复杂度均为 O ( n ) O(n) O(n)。在实际应用中,可以根据具体情况来选择最合适的方法。

💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

相关文章:

【别再困扰于LeetCode接雨水问题了 | 从暴力法=>动态规划=>单调栈】

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

酒厂酒业IP网络广播系统建设方案-基于局域网的新一代交互智慧酒厂酒业IP广播设计指南

酒厂酒业IP网络广播系统建设方案-基于局域网的新一代交互智酒业酒厂IP广播系统设计指南 由北京海特伟业任洪卓发布于2023年4月25日 一、酒厂酒业IP网络广播系统建设需求 随着中国经济的快速稳步发展&#xff0c;中国白酒行业也迎来了黄金时期&#xff0c;产品规模、销售业绩等…...

OpenHarmony JS Demo开发讲解

项目结构 打开entry→src→main→js&#xff0c;工程的开发目录如图所示 其中&#xff0c; i18n文件夹&#xff1a;用于存放配置不同语言场景的资源&#xff0c;比如应用文本词条&#xff0c;图片路径等资源。en-US.json文件定义了在英文模式下页面显示的变量内容&#xff0c…...

CentOS系统安装Intel E810 25G网卡驱动

因特尔网卡驱动给的都是二进制包&#xff0c;需要编译环境。 首先去Intel下载最新的驱动 E810驱动下载&#xff1a;https://www.intel.com/content/www/us/en/download/19630/intel-network-adapter-driver-for-e810-series-devices-under-linux.html?wapkwe810 里面有三个驱…...

Java经典的String面试题

Java经典的Spring面试题 String是基本数据类型吗&#xff1f; String你是基本数据类型String是可变的话&#xff1f; String是final类型的&#xff0c;不可变怎么比较两个字符串的值一样&#xff0c;怎么比较两个字符串是否同一对象&#xff1f; 比较字符串的值是否相同用equa…...

c# 结构体与类区别

在 C# 中&#xff0c;结构体&#xff08;struct&#xff09;和类&#xff08;class&#xff09;都是用户自定义类型&#xff0c;它们具有一些共同的特性&#xff0c;比如可以定义字段、属性、方法等。但它们也有一些区别。 下面是一些结构体和类的区别&#xff1a; 定义方式不…...

使用 patch 命令打补丁

之前的这篇文章 git 导出差异 diff 文件 写了导出 diff 、patch 文件。 拿到 patch 文件&#xff0c;用 patch 命令可以快速的把修改内容合入&#xff0c;合入后在 git 上是已修改的状态&#xff0c;如需提交还要 add 、commit 。 patch 语法 patch --help 可以看到 Usage:…...

C++——类和对象[上]

目录 1.初识面向对象 2.类的引入 3.类的定义 4.成员变量的命名规则 5.类的实例化 6.类对象模型 7.this指针 1.初识面向对象 C语言是一门面向过程的语言&#xff0c;它关注的是完成任务所需要的过程&#xff1b;C是一门面向对象的语言&#xff0c;将一个任务分为多个对…...

MySQL日志

目录 一 关于mysql的设计和运行逻辑 二 MySQL的三类日志 三 对于日志的利用 插入查询 1 备份 2 删除重复数据 一 关于mysql的设计和运行逻辑 mysql在启动的时候非常占空间&#xff0c;需要申请很大的空间&#xff0c;但是有时候内存并没有那么多&#xff0c;所以OS会把my…...

TinyURL 的加密与解密、猜数字游戏、 Fizz Buzz、相对名次----2023/4/28

TinyURL 的加密与解密----2023/4/28 TinyURL 是一种 URL 简化服务&#xff0c; 比如&#xff1a;当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时&#xff0c;它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。 加…...

Spring boot结合SkyWalking-Trace工具类实现日志打印请求链路traceid

背景&#xff1a; 随着业务的复杂化、解耦化&#xff0c;运维人员和开发人员需要对请求链路跟踪来快速发现和定位问题&#xff0c;基于应用已经集成了SkyWalking的前提下&#xff0c;如何通过获取SkyWalking生成的统一traceId并加入打印日志中&#xff0c;方便开发人员能够根据…...

精通ES=ElasticSearch

Elasticsearch 是一个分布式、高扩展、高实时的搜索与 数据分析引擎。它能很方便的使大量数据具有搜索、分析和探索的能力。充分利用Elasticsearch的水平 伸缩性&#xff0c;能使数据在 生产环境变得更有价值。Elasticsearch 的实现原理主要分为以下几个步骤&#xff0c;首先用…...

RabbitMQ-扇形交换机(Fanout )

扇形交换机&#xff1a;Fanout Exchange扇形交换机是最基本的交换机类型&#xff0c;它所能做的事情非常简单———广播消息。扇形交换机会把能接收到的消息全部发送给绑定在自己身上的队列。因为广播不需要“思考”&#xff0c;所以扇形交换机处理消息的速度也是所有的交换机类…...

Python 学习曲线 从 Python 新手到 Pro

Python 学习曲线 从 Python新手到 Pro 使用代码片段介绍&#xff1a; Python 是世界上最通用和使用最广泛的编程语言之一&#xff0c;以其简单性、可读性和多功能性而闻名。 在本文中&#xff0c;我们将探讨一系列示例场景&#xff0c;其中代码由具有三个不同专业知识水平的程序…...

薪资18K需要什么水平?来看看98年测试工程师的面试全过程…

我的情况 大概介绍一下个人情况&#xff0c;男&#xff0c;本科&#xff0c;三年多测试工作经验&#xff0c;懂python&#xff0c;会写脚本&#xff0c;会selenium&#xff0c;会性能&#xff0c;然而到今天都没有收到一份offer&#xff01;从年后就开始准备简历&#xff0c;年…...

基于趋动云的 Stable Diffusion Webui 环境搭建

Stable Diffusion Webui 环境搭建&#xff0c;首先新建一个项目&#xff1a; 然后&#xff0c;选择镜像。注意点公开的&#xff0c;已近做好的这个镜像&#xff0c;superx创建&#xff0c;集成了miniconda3的镜像。 然后选择添加数据源&#xff0c;一样&#xff0c;还是点公开&…...

备忘录设计模式解读

目录 问题引进 游戏角色状态恢复问题 传统方案解决游戏角色恢复 传统的方式的问题分析 备忘录模式基本介绍 基本介绍 备忘录模式的原理类图 对原理类图的说明 游戏角色恢复状态实例 应用实例要求 思路分析和图解(类图) 代码实战 备忘录模式的注意事项和细节 问题引…...

股票期货模拟交易有用吗?股票期货模拟交易心得

股票期货市场为了满足新用户的需求&#xff0c;有专门的股票期货模拟交易平台&#xff0c;大家可以在这个平台上进行股票期货的模拟交易&#xff0c;这样可以通过不断总结&#xff0c;丰富我们的知识。下面整理的股票期货模拟交易实验心得&#xff0c;从股票期货模拟交易与实盘…...

2023年五月份图形化三级打卡试题

活动时间 从2023年5月1日至5月21日&#xff0c;每天一道编程题。 本次打卡的规则如下&#xff1a; 小朋友每天利用10~15分钟做一道编程题&#xff0c;遇到问题就来群内讨论&#xff0c;我来给大家答疑。 小朋友做完题目后&#xff0c;截图到朋友圈打卡并把打卡的截图发到活动群…...

【华为OD机试真题】字母组合(javapython)100%通过率 详细代码注释

字母组合 知识点回溯 时间限制:1s 空间限制:256MB 限定语言:不限 题目描述: 每个数字对应多个字母,对应关系如下: 0: a,b,c 1: d,e,f 2: g,hi 3: j,k,l 4: m,n,o 5: p,q,r 6: s,t 7:u,v 8: w,x 9: y,z 输入一串数字后,通过数字和字母的对应关系可以得到多个字母字符串 (要…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...