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

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

LeetCode 503 下一个更大元素II

题目链接:https://leetcode.cn/problems/next-greater-element-ii/

思路:

方法一:两个for循环遍历单调栈

第一个for循环确定数组中的某个值在右边有最大的数,第二个for循环是为了可以使数组变成循环数组
例子:[5,4,3,2,1]
1、栈里 4,3,2,1,0](右边为栈顶,栈内元素为下标)
2、从下标0开始再次循环
(模拟一次就目标了)

代码:

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int>result(nums.size(), -1);stack<int>st;st.push(0);for(int i = 1; i < nums.size(); i++){if(nums[i] <= nums[st.top()])st.push(i);else{while(!st.empty() && nums[i] > nums[st.top()]){result[st.top()] = nums[i];st.pop();}st.push(i);}}for(int i = 0; i < nums.size(); i++){if(nums[i] <= nums[st.top()])st.push(i);else{while(!st.empty() && nums[i] > nums[st.top()]){result[st.top()] = nums[i];st.pop();}st.push(i);}}return result;}
};

方法二:单调栈,用取模的方法对数组进行循环

代码

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int>result(nums.size(), -1);stack<int>st;st.push(0);for(int i = 1; i < nums.size() * 2; i++){if(nums[i % nums.size()] <= nums[st.top()])st.push(i % nums.size());else{while(!st.empty() && nums[i % nums.size()] > nums[st.top()]){result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}}return result;}
};

总结

关键在于如何循环数组


LeetCode 42 接雨水

题目链接:https://leetcode.cn/problems/trapping-rain-water/

思路:

本题关键点:

  1. 接雨水重点在于要找当前元素左边第一个比它的元素和右边第一个比它大的元素
  2. 接雨水是按行来计算的
    在这里插入图片描述
  3. 明确h和w是如何计算的,w在计算中必须还要减1

代码

class Solution {
public:int trap(vector<int>& height) {int result = 0;stack<int>st;st.push(0);for(int i = 1; i < height.size(); i++){if(height[i] <= height[st.top()])st.push(i);else{while(!st.empty() && height[i] > height[st.top()]){int mid = st.top();st.pop();if(!st.empty()){int h = min(height[i], height[st.top()]) - height[mid];int w = i - st.top() - 1;result += h * w;}}st.push(i);}}return result;}
};

总结

接雨水问题是经典问题,后续要多加练习


今日总结:

还有一天,加油!

相关文章:

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

​ LeetCode 503 下一个更大元素II 题目链接&#xff1a;https://leetcode.cn/problems/next-greater-element-ii/ 思路&#xff1a; 方法一:两个for循环遍历单调栈 第一个for循环确定数组中的某个值在右边有最大的数&#xff0c;第二个for循环是为了可以使数组变成循环数…...

9、简单功能分析

文章目录1、静态资源访问1.1、静态资源目录1.2、如果静态资源与controller资源重名1.3、改变默认的静态资源路径1.4、修改静态资源访问前缀1.5、webjar2、欢迎页支持3、自定义 Favicon4、静态资源配置原理4.1、与Web开发有关的相关自动配置类4.2、WebMvcAutoConfiguration 注解…...

如何发送和接收参数?五种参数传递方法

通常情况下&#xff0c;我们可以使用GET或POST来发送请求和数据&#xff0c;但GET和POST两种方法所携带的数据都是比较简单的数据&#xff0c;接下来在我们这个基础上&#xff0c;列举5种比较负责的参数传递方法&#xff0c;并对这些参数如何发送&#xff0c;后台改如何接收做详…...

蓝桥杯C/C++VIP试题每日一练之矩形面积交

💛作者主页:静Yu 🧡简介:CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家,前端知识交流社区创建者 💛社区地址:前端知识交流社区 🧡博主的个人博客:静Yu的个人博客 🧡博主的个人笔记本:前端面试题 个人笔记本只记录前端领域的面试题目,项目总结,面试技…...

Spark大数据处理讲课笔记2.4 IDEA开发词频统计项目

文章目录零、本讲学习目标一、词频统计准备工作&#xff08;一&#xff09;启动集群的HDFS与Spark&#xff08;二&#xff09;在HDFS上准备单词文件二、本地模式执行Spark程序&#xff08;一&#xff09;创建Maven项目&#xff08;二&#xff09;添加Spark相关依赖&#xff0c;…...

【ChatGPT 】国内无需注册 openai 即可访问 ChatGPT:ChatGPT Sidebar 浏览器扩展程序的安装与使用

一、前言 问题&#xff1a;国内注册 openai 账号麻烦&#xff0c;新必应有部分人也无法登录成功&#xff0c;存在域名单点登录失败等问题&#xff0c;所以无法真正使用 ChatGPT 解决&#xff1a;大部分人仅需使用 ChatGPT 的搜索功能&#xff0c;无需真正对话&#xff0c;需要…...

使用fetch()异步请求API数据实现汇率转换器

任务8 https://segmentfault.com/a/1190000038998601 https://chinese.freecodecamp.org/news/how-to-master-async-await-with-this-real-world-example/ 跟随上面的指示&#xff0c;理解异步函数的编写&#xff0c;并且实现这个汇率转换器。 第一步&#xff1a;在工作区初始…...

GPT-4“王炸”,10秒钟开发一套Web + APP 系统

10秒钟做出一个网站 一则有关GPT4发布会的视频在网上流传&#xff0c;这则两分钟的视频演示的内容是&#xff1a; 1. 在草稿本上用纸笔画出一个非常粗糙的草图&#xff1b; 2. 拍照告诉 GPT 我们要做一个网站&#xff0c;效果正如图所示&#xff0c;让其生成网站代码&#xff1…...

Disjoint 集合数据结构或 Union-Find 算法简介

联合查找算法是一种对此类数据结构执行两个有用操作的算法&#xff1a; 查找&#xff1a;确定特定元素在哪个子集中。这可用于确定两个元素是否在同一子集中。联合&#xff1a;将两个子集连接成一个子集。这里首先我们必须检查这两个子集是否属于同一个集合。如果否&#xff0c…...

uniapp中nvue与vue的区别?

文章目录简介nvue 和 vue 相互通讯方式&#xff1a;nvue注意事项&#xff1a;简介 uni-app是逻辑渲染分离的&#xff0c;渲染层在app端提供了两套排版引擎&#xff0c; 小程序方式的webview渲染和weex方式的原生渲染&#xff0c;两种渲染引入可以自己根据需要选。 vue文件走的…...

带头双向循环链表的实现

1.结构体的创建以及类型重定义 typedef int LTDataType; typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next; }LTNode;2.链表的初始化 这个函数用于创建节点&#xff0c;后面还会用到。 LTNode* BuyListNode(LTDataType x) {LTNode* n…...

大屏使用dv-digital-flop定时刷新显示总人数

本文在基础上进行改进&#xff0c;后端使用若依后端IofTV-Screen: &#x1f525;一个基于 vue、datav、Echart 框架的物联网可视化&#xff08;大屏展示&#xff09;模板&#xff0c;提供数据动态刷新渲染、屏幕适应、数据滚动配置&#xff0c;内部图表自由替换、Mixins注入等功…...

Java面向对象部分 个人学习记录

注:此博客是个人学习记录&#xff0c;会有错的地方&#xff0c;面向对象部分我可能会画很多图来加深我的理解 不引出了&#xff0c;直接开始 class Dog{String name;int age;String type;public Dog(String name,int age,String type){this.namename;this.ageage;this.typetyp…...

MySQL数据库——对Linux MySQL软件包的一些说明

Linux 操作系统的发行版很多&#xff0c;不同发行版下的 MySQL 版本也是不同的。MySQL 主要支持的 Linux 版本有 Red Hat Enterprise Linux 和 SUSE Linux Enterprise Server。这里主要介绍不同 Linux 发行版下 MySQL 支持的版本。 Linux 操作系统的 MySQL 软件包一般分为以下…...

【JavaEE进阶】——第二节.Spring核心和设计思想

文章目录 前言 一、Spring是什么&#xff1f; 二、什么是容器&#xff1f; 三、什么是IoC? 3.1 初始loC 3.2 举例解释loC 3.3 Spring IoC思想的体现 四、什么是DI&#xff1f; 4.1DI的概念 4.2 Ioc和DI的区别 总结 前言 今天我们将进入到有关spring的认识当中&…...

twitter开源算法(1)For You推荐系统架构

1 Twitter’s Recommendation Algorithm 我们的推荐系统由许多互相关联的服务(services)和工作&#xff08;jobs&#xff09;组成,本节这要是聚焦home timeline的for you feed流。 the-algorithm开源地址&#xff1a;https://github.com/twitter/the-algorithm 本篇博客来源&…...

A General Framework for Uncertainty Estimation in Deep Learning源码阅读(二)

接上文 ResNet定义&#xff1a; 代码使用 def ResNet18ADF(noise_variance1e-3, min_variance1e-3):return ResNet(BasicBlock, [2,2,2,2], num_classes10, noise_variance1e-3, min_variance1e-3, initialize_msraFalse)定义模型&#xff0c;其中ResNet定义为&#xff1a; …...

串行通信协议---HART协议

实际应用中&#xff0c;HART协议是仅次于Modbus协议的最接近统一现场总线的标准&#xff0c;主要是在4~20mA电流信号上面叠加数字信号&#xff0c;物理层采用Bell 202标准的FSK技术成功实现模拟信号和数字信号双向同时通信而互不干扰。HART协议规定了传输的物理形式、消息结构、…...

【独家】华为OD机试 - 寻找密码(C 语言解题)

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本期题目:寻找密码 题目 小王在进行游…...

FPGA有哪些优质的带源码的IP开源网站?

这是某乎上的一个问题&#xff0c;我觉得还不错&#xff0c;今天就系统性的总结一下1、fpga4funhttps://www.fpga4fun.com/你能在这个网站上找到什么&#xff1f;您可以找到信息页面&#xff0c;以及使用 FPGA 板构建的 FPGA 项目。注重点&#xff1a;项目。FPGA 项目使用一种称…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...