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

算法训练第五十九天|503. 下一个更大元素 II、42. 接雨水

503. 下一个更大元素 II:

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

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

示例 :

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2

解答:

class Solution {public int[] nextGreaterElements(int[] nums) {int[] res = new int[nums.length];Arrays.fill(res,-1);Stack<Integer> stack = new Stack<>();int size = nums.length;stack.push(0);for (int i = 1; i <2*nums.length ; i++) {while (!stack.isEmpty()&&nums[i%size]>nums[stack.peek()]){res[stack.peek()] = nums[i%size];stack.pop();}stack.push(i%size);}return res;}
}

算法总结:

本题实际上和下一个更大元素Ⅰ那题思路是一样的,唯一的区别在于我们要考虑循环的问题,我们可以通过2*nums.length来扩大遍历的次数,再通过取模的方式来实现更新。

42. 接雨水:

题目链接
给定 n 个非负整数表示每个宽度为 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 个单位的雨水(蓝色部分表示雨水)。

解答:

class Solution {public int trap(int[] height) {int size = height.length;if (size <= 2) return 0;// in the stack, we push the index of array// using height[] to access the real heightStack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int index = 1; index < size; index++){int stackTop = stack.peek();if (height[index] < height[stackTop]){stack.push(index);}else if (height[index] == height[stackTop]){// 因为相等的相邻墙,左边一个是不可能存放雨水的,所以pop左边的index, push当前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint heightAtIdx = height[index];while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){int mid = stack.pop();if (!stack.isEmpty()){int left = stack.peek();int h = Math.min(height[left], height[index]) - height[mid];int w = index - left - 1;int hold = h * w;if (hold > 0) sum += hold;stackTop = stack.peek();}}stack.push(index);}}return sum;}
}

算法总结:

接雨水这题因为我们要考虑的是凹槽的空间,所以实际上我们只要找到下一个比当前柱子大的柱子即可,所以本题本质上和前面考虑的问题是一样的,同时用int h = Math.min(height[left], height[index]) - height[mid];来计算当前存储的高度,最后加入sum中即为最终结果。

相关文章:

算法训练第五十九天|503. 下一个更大元素 II、42. 接雨水

503. 下一个更大元素 II&#xff1a; 题目链接 给定一个循环数组 nums &#xff08; nums[nums.length - 1] 的下一个元素是 nums[0] &#xff09;&#xff0c;返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序&#xff0c;这个数字之…...

mysql之数据类型、建表以及约束

目录 一. CRUD 1.1 什么是crud 1.2 select(查询) 1.3 INSERT(新增) 1.4 UPDATE(修改&#xff09; 1.5 DELETE(删除) 二. 函数 2.1 常见函数 2.2 流程控制函数 2.3聚合函数 三. union与union all 3.1 union 3.2 union all 3.3 具体不同 3.4 结论 四、思维导图 一. CRUD 1.1…...

复试 || 就业day04(2024.01.05)项目一

文章目录 前言线性回归房价预测加载数据数据查看数据拆分数据建模模型的验证、应用模型的评估 总结 前言 &#x1f4ab;你好&#xff0c;我是辰chen&#xff0c;本文旨在准备考研复试或就业 &#x1f4ab;本文内容来自某机构网课&#xff0c;是我为复试准备的第一个项目 &#…...

华为机试真题实战应用【赛题代码篇】-最小传输时延(附python、C++和JAVA代码实现)

目录 问题描述 输入描述: 输出描述: 知识储备 解题思路 思路一...

C++ 运算符重载

&#xff08;Operator&#xff09; 加分 减法 []的重载 #include <iostream> using namespace std;class time1 {public:time1(){shi0;fen0;miao0;}time1(int shi, int fen, int miao){this->shi shi;this->fen fen;this->miao miao;}time1 operator (ti…...

vue3学习 【2】vite起步和开发工具基本配置

vite的简介 官方文档 刚起步学习&#xff0c;所以我们只需要按照官方文档的入门流程即可。推荐阅读一下官网的为什么使用vite vite目前需要的node版本是18&#xff0c;可以参考上一篇文章的安装nvm&#xff0c;用来进行多版本的node管理。 vite安装与使用 npm create vitela…...

计算机创新协会冬令营——暴力枚举题目06

我给大家第一阶段的最后一道题就到这里了&#xff0c;下次得过段时间了。所以这道题简单一点。但是足够经典 下述题目描述和示例均来自力扣&#xff1a;两数之和 题目描述 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target …...

单片机快速入门

参考连接&#xff1a; 安装MinGW-64&#xff08;在win10上搭建C/C开发环境&#xff09;https://zhuanlan.zhihu.com/p/85429160MinGW-64; 链接&#xff1a;https://pan.baidu.com/s/1oE1FmjyK7aJPnDC8vASmCg?pwdy1mz 提取码&#xff1a;y1mz --来自百度网盘超级会员V7的分享C…...

Eureka相关问题及答案(2024)

1、什么是Eureka&#xff1f; Eureka是一个由Netflix开发的服务发现&#xff08;Service Discovery&#xff09;工具&#xff0c;它是Spring Cloud生态系统中的一个关键组件。服务发现是微服务架构中的一个重要概念&#xff0c;它允许服务实例在启动时注册自己&#xff0c;以便…...

Django 7 实现Web便签

一、效果图 二、会用到的知识 目录结构与URL路由注册request与response对象模板基础与模板继承ORM查询后台管理 三、实现步骤 1. terminal 输入 django-admin startapp the_10回车 2. 注册&#xff0c; 在 tutorial子文件夹settings.py INSTALLED_APPS 中括号添加 "the…...

Jenkins集成部署java项目

文章目录 Jenkins简介安装 Jenkins简介 Jenkins能实时监控集成中存在的错误&#xff0c;提供详细的日志文件和提醒功能&#xff0c;还能用图表的形式形象的展示项目构建的趋势和稳定性。 官网 安装 在官网下载windows版本的Jenkins 但是我点击这里浏览器没有反应&#xff0…...

FFmpeg之——获取上传视频的尺寸(长、宽)

获取上传视频的尺寸&#xff1a; 获取视频尺寸通常需要借助第三方库FFmpeg。 首先&#xff0c;确保你的系统中已安装了FFmpeg&#xff0c;并且FFmpeg的可执行文件路径已经添加到你的系统环境变量中。 1.官网下载ffmpeg 进入 链接: ffmpeg官网 网址&#xff0c;点击下载wind…...

Ajax学习

文章目录 AjaxAjax 是什么Ajax 经典应用场景Ajax 原理示意图ajax的异步请求的方法ajax的逻辑:应用实例-验证用户名是否存在思路框架图:需求分析: 到数据库去验证用户名是否可用思路框架图大功告成:使用JQuery-Ajax实现上面相同的需求:Ajax Ajax 是什么 AJAX 即"Async…...

排序算法——关于快速排序的详解

目录 1.基本思想 2.基本原理 2.1划分思想 2.2排序过程 &#xff08;1&#xff09;选择基准值 &#xff08;2&#xff09;分割过程&#xff08;Partition&#xff09; &#xff08;3&#xff09;递归排序 &#xff08;4&#xff09;合并过程 2.3具体实例 2.4实现代码 2.5关键要…...

序言:《未来已来》

尊敬的读者&#xff0c; 你是否曾经在面对冗长的报告、繁琐的工作、沉重的生活压力时感到困扰&#xff0c;渴望找到一种方式来提升效率&#xff0c;释放压力&#xff1f;你是否曾经在自我创业的道路上&#xff0c;苦于找不到有效的市场营销方式&#xff0c;寻求突破&#xff1f…...

【Spring实战】22 Spring Actuator 入门

文章目录 1. 定义2. 功能3. 依赖4. 配置5. 常用的应用场景1&#xff09;环境监控2&#xff09;运维管理3&#xff09;性能优化 结论 Spring Actuator 是 Spring 框架的一个模块&#xff0c;为开发人员提供了一套强大的监控和管理功能。本文将深入探讨 Spring Actuator 的定义、…...

JSON安全性

确保JSON处理的安全性是现代Web开发中重要的一环。以下是一些关键的安全实践&#xff0c;用于防止JSON注入攻击以及确保数据在传输过程中的安全性&#xff1a; 1. **验证和清洗输入&#xff1a;** - 在将任何数据写入数据库之前&#xff0c;请确保验证用户输入。对于期望的JSON…...

spring-boot-maven插件repackage(goal)的那些事

前言&#xff1a;在打包Springboot项目成jar包时需要在pom.xml使用spring-boot-maven-plugin来增加Maven功能&#xff0c;在我的上一篇博客<<Maven生命周期和插件的那些事&#xff08;2021版&#xff09;>>中已经介绍过Maven和插件的关系&#xff0c;在此不再赘述&…...

ubuntu的boot分区被删除恢复

在鼓捣黑苹果的时候&#xff0c;误删了ubuntu的boot分区&#xff0c;进系统的时候出现emergency mode&#xff0c;那么现在来讲讲怎么恢复 首先做一个ubuntu的启动盘&#xff0c;然后进入启动盘的系统选择试用 呼出命令行&#xff0c;然后添加一个源 sudo add-apt-repository…...

【userfaultfd 条件竞争】starCTF2019 - hackme

前言 呜呜呜&#xff0c;这题不难&#xff0c;但是差不多一个多月没碰我的女朋友 kernel pwn 了&#xff0c;对我的 root 宝宝也是非常想念&#xff0c;可惜这题没有找到我的 root 宝宝&#xff0c;就偷了她的 flag。 哎有点生疏了&#xff0c;这题没看出来堆溢出&#xff0c…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

JS红宝书笔记 - 3.3 变量

要定义变量&#xff0c;可以使用var操作符&#xff0c;后跟变量名 ES实现变量初始化&#xff0c;因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符&#xff0c;可以创建一个全局变量 如果需要定义…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

Python爬虫实战:研究Restkit库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...

【动态规划】B4336 [中山市赛 2023] 永别|普及+

B4336 [中山市赛 2023] 永别 题目描述 你做了一个梦&#xff0c;梦里有一个字符串&#xff0c;这个字符串无论正着读还是倒着读都是一样的&#xff0c;例如&#xff1a; a b c b a \tt abcba abcba 就符合这个条件。 但是你醒来时不记得梦中的字符串是什么&#xff0c;只记得…...

AI书签管理工具开发全记录(十八):书签导入导出

文章目录 AI书签管理工具开发全记录&#xff08;十八&#xff09;&#xff1a;书签导入导出1.前言 &#x1f4dd;2.书签结构分析 &#x1f4d6;3.书签示例 &#x1f4d1;4.书签文件结构定义描述 &#x1f523;4.1. ​整体文档结构​​4.2. ​核心元素类型​​4.3. ​层级关系4.…...