当前位置: 首页 > 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…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001

qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类&#xff0c;直接把源文件拖进VS的项目里&#xff0c;然后VS卡住十秒&#xff0c;然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分&#xff0c;导致编译的时候找不到了。因…...

用js实现常见排序算法

以下是几种常见排序算法的 JS实现&#xff0c;包括选择排序、冒泡排序、插入排序、快速排序和归并排序&#xff0c;以及每种算法的特点和复杂度分析 1. 选择排序&#xff08;Selection Sort&#xff09; 核心思想&#xff1a;每次从未排序部分选择最小元素&#xff0c;与未排…...

【Qt】控件 QWidget

控件 QWidget 一. 控件概述二. QWidget 的核心属性可用状态&#xff1a;enabled几何&#xff1a;geometrywindows frame 窗口框架的影响 窗口标题&#xff1a;windowTitle窗口图标&#xff1a;windowIconqrc 机制 窗口不透明度&#xff1a;windowOpacity光标&#xff1a;cursor…...