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

代码随想录算法训练营第五九天 | 下一个更大元素II、接雨水

目录

  • 下一个更大元素II
  • 接雨水

LeetCode 503.下一个更大元素II
LeetCode 42. 接雨水

下一个更大元素II

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1 。

  • 问题的关键在于在遍历的过程中模拟走了两遍 nums
class Solution {public int[] nextGreaterElements(int[] nums) {Deque<Integer> stack = new LinkedList<>();int[] res = new int[nums.length];Arrays.fill(res, -1);stack.push(0);int length = nums.length;for (int i = 0; i < length * 2; i++) {            while (!stack.isEmpty() && nums[i % length] > nums[stack.peek()]) {res[stack.peek()] = nums[i % length];stack.pop();}stack.push(i % length);}return res;}
}

接雨水

  • 暴力
    • 也是使用双指针。
    • 按照列来计算的话,宽度一定是1了,我们再把每一列的雨水的高度求出来就可以了。
    • 只要记录左边柱子的最高高度 和 右边柱子的最高高度,就可以计算当前位置的雨水面积,这就是通过列来计算。
    • 当前列雨水面积:min(左边柱子的最高高度,记录右边柱子的最高高度) - 当前柱子高度。 min(lHeight, rHeight) - height。
    • 只要从头遍历一遍所有的列,然后求出每一列雨水的体积,相加之后就是总雨水的体积了。
    • 时间复杂度为 O ( n 2 ) O(n^2) O(n2),空间复杂度为 O ( 1 ) O(1) O(1)超时

在这里插入图片描述

class Solution {public int trap(int[] height) {// 暴力int sum = 0;for (int i = 0; i < height.length; i++) {// 第一个柱子和最后一个柱子不接水if(i == 0 || i == height.length - 1) continue;int rHeight = height[i]; // 记录右边柱子的最高高度int lHeight = height[i]; // 记录左边柱子的最高高度for (int r = i + 1; r < height.length; r++){rHeight = Math.max(rHeight, height[r]);}for (int l = i - 1; l >= 0; l--){lHeight = Math.max(lHeight, height[l]);}int h = Math.min(rHeight, lHeight) - height[i];if (h > 0) sum += h;}return sum;}
}
  • 双指针优化

    • 优化思路是讲取左侧最高高度和右侧最高高度脱离出来,提前处理
    • 暴力解法中,为了得到两边的最高高度,使用了双指针来遍历,每到一个柱子都向两边遍历一遍,这其实是有重复计算的。
    • 我们把每一个位置的左边最高高度记录在一个数组上(maxLeft),右边最高高度记录在一个数组上(maxRight),这样就避免了重复计算。
    • 从左向右遍历:maxLeft[i] = max(height[i], maxLeft[i - 1]);
    • 从右向左遍历:maxRight[i] = max(height[i], maxRight[i + 1]);
class Solution {public int trap(int[] height) {// 双指针优化if (height.length <= 2) return 0;int[] maxLeft = new int[height.length];int[] maxRight = new int[height.length];int length = height.length;// 记录每个柱子左边柱子的最大高度maxLeft[0] = height[0];for (int i = 1; i < length; i++) {maxLeft[i] = Math.max(height[i], maxLeft[i-1]);}// 记录每个柱子右边柱子的最大高度maxRight[length-1] = height[length-1];for (int i = length-2; i >= 0; i--) {maxRight[i] = Math.max(height[i], maxRight[i+1]);}// 求和int sum = 0;for (int i = 0; i < length; i++) {int count = Math.min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}
}
  • 单调栈
    • 单调栈就是保持栈内元素有序,需要自己维持顺序。
    • 通常是一维数组,要寻找任一个元素的右边或左边第一个比自己大或者小的元素的位置,此时用单调栈。

在这里插入图片描述

class Solution {public int trap(int[] height) {if (height.length <= 2) return 0;Stack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int i = 1; i < height.length; i++) {if (height[i] < height[stack.peek()]) {stack.push(i);}else if (height[i] == height[stack.peek()]) {stack.pop();stack.push(i);}else {// pop up all lower valuewhile (!stack.isEmpty() && height[i] > height[stack.peek()]) {int mid = stack.peek();stack.pop();if (!stack.isEmpty()) {int h = Math.min(height[stack.peek()], height[i]) - height[mid];int w = i - stack.peek() - 1;int hold = h * w;if (hold > 0) sum += hold;}}stack.push(i);}}return sum;}
}

相关文章:

代码随想录算法训练营第五九天 | 下一个更大元素II、接雨水

目录 下一个更大元素II接雨水 LeetCode 503.下一个更大元素II LeetCode 42. 接雨水 下一个更大元素II 给定一个循环数组 nums &#xff08; nums[nums.length - 1] 的下一个元素是 nums[0] &#xff09;&#xff0c;返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一…...

LeetCode(力扣)算法题_2864_最大二进制奇数

最大二进制奇数 题目描述 给你一个 二进制 字符串 s &#xff0c;其中至少包含一个 1 。 你必须按某种方式 重新排列 字符串中的位&#xff0c;使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。 以字符串形式&#xff0c;表示并返回可以由给定组合生成的最大二进…...

食药物质创新 赋能中式滋补健康产业发展交流会圆满结束

3月5日&#xff0c;“食药物质创新 赋能中式滋补健康产业发展交流会”在山东国际会展中心召开。本次会议由中国生物发酵产业协会主办&#xff0c;浙江科技大学、未名太研生物科技(绍兴)有限公司承办&#xff0c;汇乐达供应链服务(常州)有限责任公司支持。本次论坛旨在加强行业创…...

用好大模型、承载“头雁领航”使命,央企如何三路出击?

作者 | 曾响铃 文 | 响铃说 智能化成为两会热议话题&#xff0c;2024政府工作报告中也直接提到要深化大数据、人工智能等研发应用&#xff0c;开展“人工智能”行动。 毫无疑问&#xff0c;大模型热潮下&#xff0c;以智能化推进传统产业升级已经成为普遍共识。 具体如何做…...

LabVIEW飞机液压基础试验台测试系统

LabVIEW飞机液压基础试验台测试系统 为解决飞机液压基础实验台人工控制操作复杂、测试时间长、测试流程易出错等问题&#xff0c;开发了一套基于LabVIEW的飞机液压基础试验台测试系统。该系统通过计算机控制&#xff0c;实现了高度自动化的测试流程&#xff0c;有效提高了测试…...

STM32第十课:串口发送

一、usart串口 1.1 USART串口协议 串口通讯(Serial Communication) 是一种设备间非常常用的串行通讯方式&#xff0c;因为它简单便捷&#xff0c;因此大部分电子设备都支持该通讯方式&#xff0c;电子工程师在调试设备时也经常使用该通讯方式输出调试信息。在计算机科学里&…...

淘宝扭蛋机小程序:探索未知的惊喜之旅

你是否曾在商场里被那闪闪发光的扭蛋机吸引&#xff0c;却因为种种原因无法下手&#xff1f;现在&#xff0c;淘宝扭蛋机小程序带给你全新的扭蛋体验&#xff0c;让你随时随地都能感受到那份未知的惊喜。 淘宝扭蛋机小程序是一款集娱乐与购物于一体的全新应用。它汇聚了众多热…...

[nlp入门论文精读] | Transformer

写在前面 最近工作从CV转向了NLP&#xff0c;于是空余时间便跟着哔哩哔哩李沐老师的视频学习。其实研一NLP课程讲论文的时候&#xff0c;我们小组就选择了经典的Attention和Bert&#xff0c;但还有很多细节并不完全理解&#xff0c;实际使用时也很困惑。 因此这个系列就来记…...

科技回顾,飞凌嵌入式受邀亮相第八届瑞芯微开发者大会「RKDC2024」

2024年3月7日~8日&#xff0c;第八届瑞芯微开发者大会&#xff08;RKDC2024&#xff09;在福州举行&#xff0c;本届大会以“AI芯片AI应用AloT”为主题&#xff0c;邀请各行业的开发者共启数智化未来。 本届大会亮点颇多&#xff0c;不仅有13大芯片应用展示、9场产品和技术论坛…...

代码随想录算法训练营第五十九天丨503. 下一个更大元素 II、42. 接雨水

503. 下一个更大元素 II 还是比较容易想的&#xff0c;扩展数组一倍即可。 class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:extended_nums nums * 2n len(nums)mono []res [- 1] * nfor i, num in enumerate(extended_nums):while mono…...

全代码分享|R语言孟德尔随机化怎么做?TwoSampleMR包MR一套标准流程

文章目录 1.前言1.1 成立条件1.2 三大要素1.3 统计原理 2.demo2.1 加载R包2.2 主要MR分析2.3 MR补充分析、多态性、验证 2.4 结果可视化 1.前言 孟德尔随机化(Mendelian randomization&#xff0c;MR)是一种利用基因变异作为工具变量来评估暴露与结果之间因果关系的统计方法。…...

【AI视野·今日NLP 自然语言处理论文速览 第八十四期】Thu, 7 Mar 2024

AI视野今日CS.NLP 自然语言处理论文速览 Thu, 7 Mar 2024 Totally 52 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers The Heuristic Core: Understanding Subnetwork Generalization in Pretrained Language Models Authors Adith…...

英伟达推出免训练,可生成连贯图片的文生图模型ConsiStory,生成角色一致性解决新方案

目前&#xff0c;多数文生图模型皆使用的是随机采样模式&#xff0c;使得每次生成的图像效果皆不同&#xff0c;在生成连贯的图像方面非常差。 例如&#xff0c;想通过AI生成一套图像连环画&#xff0c;即便使用同类的提示词也很难实现。虽然DALLE 3和Midjourney可以对图像实现…...

Jmeter 性能 —— 50TPS与秒杀分析!

1、50tps——5tps分析 50tps基本上已经满足了大部分中小型企业要求了 需求&#xff1a;期望我项目的接口&#xff0c;都要能满足50tps&#xff1f; 算 50tps&#xff1a;50 个事务每秒50 t/s 1分钟&#xff1a;50\*60s 3000 事务1小时 3000 \* 60 180000 事务 1小时要处理…...

【前端】如何计算首屏及白屏时间

文章目录 一、首屏时间二、白屏时间 一、首屏时间 白屏时间&#xff1a;页面渲染完所有内容的时间 简单点就是在<body> 标签后写js代码计算&#xff0c;但是不是很准确 <head><title>白屏时间</title> </head> <body></body> <s…...

重学SpringBoot3-ServletWebServerFactoryAutoConfiguration类

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-ServletWebServerFactoryAutoConfiguration类 工作原理关键组件以TomcatServletWebServerFactory为例ServletWebServerFactory会创建webServer的时机关键…...

FileZillaClient连接被拒绝,无法连接

1.ECONNREFUSED - 连接被服务器拒绝 2、无法连接FZ时&#xff0c;判断没有ssh 更新源列表&#xff1a; sudo apt-get update 安装 openssh-server &#xff1a;sudo apt-get install openssh-server 查看是否启动ssh&#xff1a;sudo ps -e | grep ssh...

每日一面——成员初始化列表、移动构造和拷贝构造

写前声明&#xff1a;参考链接 C面经、面试宝典 等 ✊✊✊每日一面——成员初始化列表、移动构造和拷贝构造 一、类成员初始化方式&#xff1f;构造函数的执行顺序&#xff1f;为什么用成员初始化列表会快一些&#xff1f;二、final和override关键字三、拷贝初始化和直接初始化…...

OPC UA 服务器的Web访问

基于Web 的应用非常普及&#xff0c;例如基于web 的SCADA &#xff0c;物联网 Dashboard 等等&#xff0c;那么基于Web 的应用如何访问OPC UA 服务器呢&#xff1f;本博文讨论这方面的问题。 Web 的通信方式 Web 是我们通常讲的网站&#xff0c;它由浏览器&#xff0c;HTTP 服…...

docker 子网

当需要给容器分配指定 ip &#xff0c;为避免ip 冲突&#xff0c;指定容器子网处理 创建 subnet 子网 docker network create --subnet 10.0.0.0/24 --gateway 10.0.0.1 subnet-testdocker network ls NETWORK ID NAME DRIVER SCOPE ... f582ecf297bc sub…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...