【算法与数据结构】496、503、LeetCode下一个更大元素I II
文章目录
- 一、496、下一个更大元素 I
- 二、503、下一个更大元素II
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、496、下一个更大元素 I

思路分析:本题思路和【算法与数据结构】739、LeetCode每日温度类似。如果用暴力破解法时间复杂度需要 O ( m ∗ n ) O(m*n) O(m∗n),其中 m m m和 n n n分别是两个数组的长度。单调栈只需要 O ( n + m ) O(n+m) O(n+m)的时间复杂度。相较于739题,本题需要找到nums1元素在nums2数组中的位置,那么我们可以利用unordered_map,查找和增删效率是最高的【算法与数据结构】算法与数据结构知识点:
unordered_map<int, int> umap; // key:下标元素,value:下标for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}
然后利用739题的单调栈思路,遍历nums2数组。每当当前遍历元素大于栈顶元素,并且nums2数组的元素在nums1中存在(umap.count(nums2[st.top()]) > 0就是统计数量,大于零说明nums2[st.top()]元素存在),我们找到栈顶元素在nums1中的下标,在结果数组中根据下标修改其值:
for (int i = 0; i < nums2.size(); i++) { while (!st.empty() && nums2[i] > nums2[st.top()]) {if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素,count函数计算数量int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] = nums2[i];}st.pop();}st.push(i); // 插入数组的下标}
程序如下:
// 496、下一个更大元素 I
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(), -1);stack<int> st;unordered_map<int, int> umap; // key:下标元素,value:下标for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}for (int i = 0; i < nums2.size(); i++) { while (!st.empty() && nums2[i] > nums2[st.top()]) {if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素,count函数计算数量int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] = nums2[i];}st.pop();}st.push(i); // 插入数组的下标}return result;}
};
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( n ) O(n) O(n)。
二、503、下一个更大元素II

思路分析:本题和496题不同之处在于从两个数组变成一个数组,然后数组是环形数组。针对环形数组,我们要比较大小,可以将环形数组复制一份,两个相同的数组扩充成一个新数组。然后在新数组上去做单调栈的操作。
程序如下:
// 503、下一个更大元素II-版本一
class Solution2 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> nums1(nums.begin(), nums.end()); // 拼接一个新的numsnums.insert(nums.end(), nums1.begin(), nums1.end()); vector<int> result(nums.size(), -1); // 用新的nums大小来初始化result// 开始单调栈stack<int> st;st.push(0);for (int i = 1; i < nums.size(); i++) {while (!st.empty() && nums[i] > nums[st.top()]) {result[st.top()] = nums[i];st.pop();}st.push(i);}result.resize(nums.size() / 2); // 最后再把结果集即result数组resize到原数组大小return result;}
};
虽然这种写法比较直观,但是做了很多无用操作。resize函数是O(1)的操作,但扩充nums数组相当于多了一个O(n)的操作。其实也可以不扩充nums,而是在遍历的过程中模拟走了两边nums。例如我们改变索引的上界,然后令其做取nums.size()模的操作。
// 503、下一个更大元素II-版本二
class Solution3 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);stack<int> st;for (int i = 0; i < nums.size() * 2; i++) {// 模拟遍历两边nums,注意一下都是用i % nums.size()来操作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;}
};
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( n ) O(n) O(n)。
三、完整代码
# include <iostream>
# include <vector>
# include <unordered_map>.
# include <stack>
using namespace std;// 496、下一个更大元素 I
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(), -1);stack<int> st;unordered_map<int, int> umap; // key:下标元素,value:下标for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}for (int i = 0; i < nums2.size(); i++) { while (!st.empty() && nums2[i] > nums2[st.top()]) {if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素,count函数计算数量int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] = nums2[i];}st.pop();}st.push(i); // 插入数组的下标}return result;}
};// 503、下一个更大元素II-版本一
class Solution2 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> nums1(nums.begin(), nums.end()); // 拼接一个新的numsnums.insert(nums.end(), nums1.begin(), nums1.end()); vector<int> result(nums.size(), -1); // 用新的nums大小来初始化result// 开始单调栈stack<int> st;st.push(0);for (int i = 1; i < nums.size(); i++) {while (!st.empty() && nums[i] > nums[st.top()]) {result[st.top()] = nums[i];st.pop();}st.push(i);}result.resize(nums.size() / 2); // 最后再把结果集即result数组resize到原数组大小return result;}
};// 503、下一个更大元素II-版本二
class Solution3 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);if (nums.size() == 0) return result;stack<int> st;for (int i = 0; i < nums.size() * 2; i++) {// 模拟遍历两边nums,注意一下都是用i % nums.size()来操作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;}
};int main() {//vector<int> nums1 = { 4,1,2 };//vector<int> nums2 = { 1,3,4,2 };//Solution s1;//vector<int> result = s1.nextGreaterElement(nums1, nums2);vector<int> nums = { 1,2,3,4,3 };Solution2 s1;vector<int> result = s1.nextGreaterElements(nums);for (vector<int>::iterator i = result.begin(); i != result.end(); i++) {cout << *i << " ";}cout << endl;system("pause");return 0;
}
end
相关文章:
【算法与数据结构】496、503、LeetCode下一个更大元素I II
文章目录 一、496、下一个更大元素 I二、503、下一个更大元素II三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、496、下一个更大元素 I 思路分析:本题思路和【算法与数据结构】739、LeetCode每日温度类似…...
当AGI遇到人形机器人
为什么人类对人形机器人抱有执念 人形机器人是一种模仿人类外形和行为的机器人,它的研究和开发有着多方面的目的和意义。 人形机器人可以更好地适应人类的环境和工具。人类的生活和工作空间都是根据人的尺寸和动作来设计的,例如门、楼梯、桌椅、开关等…...
Pytorch卷积层原理和示例 nn.Conv1d卷积 nn.Conv2d卷积
内容列表 一,前提 二,卷积层原理 1.概念 2.作用 3. 卷积过程 三,nn.conv1d 1,函数定义: 2, 参数说明: 3,代码: 4, 分析计算过程 四,nn.conv2d 1, 函数定义 2, 参数: 3, 代码 4, 分析计算过程 …...
Qt 实现无边框窗口1.0
目录 项目需求: 1、没有边框; 2、点击windows系统的状态栏的程序运行图标可实现最大最小化; 3、可以移动窗口; 项目实现: 1、实现 无边框 2、实现 点击windows系统的状态栏的程序运行图标可实现最大最小化 3、实现 窗…...
Flume(二)【Flume 进阶使用】
前言 学数仓的时候发现 flume 落了一点,赶紧补齐。 1、Flume 事务 Source 在往 Channel 发送数据之前会开启一个 Put 事务: doPut:将批量数据写入临时缓冲区 putList(当 source 中的数据达到 batchsize 或者 超过特定的时间就会…...
静态时序分析:SDC约束命令set_clock_transition详解
相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 在静态时序分析:SDC约束命令create_clock详解一文的最后,我们谈到了针对理想(ideal)时钟,可以使用set_clock_transition命令直…...
web 发展阶段 -- 详解
1. web 发展阶段 当前处于 移动 web 应用阶段。也是个风口(当然是针对有能力创业的人来说的),如 抖音、快手就是这个时代的产物。 2. web 发展阶段引出前后端分离的过程 2.1 传统开发方式 2.2 前后端分离模式 衍生自移动 web 应用阶段。 3.…...
车载软件架构 —— Adaptive AUTOSAR软件架构中操作系统
车载软件架构 —— Adaptive AUTOSAR软件架构中操作系统 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师&…...
前缀和算法-截断数组
5057. 截断数组 - AcWing题库 给定一个长度为 n 的正整数数组 a1,a2,…,an 和一个正整数 p。 现在,要将该数组从中间截断,得到两个非空子数组。 我们规定,一个数组的价值等于数组内所有元素之和模 p 的结果。 我们希望,将给定数组…...
Kubernetes实战:Kubernetes中网络插件calico Daemon Sets显示异常红色
目录 一、排查步骤与解决方案1.1、POD排查问题定位1.2、针对问题解决错误1.3、继续针对问题解决错误 一、排查步骤与解决方案 1.1、POD排查问题定位 我的k8s集群由3个节点组成的,calico在每个节点上都有一个pod,通过kubectl get pod -A命令发现有一个pod的READY 为…...
深入探究:JSONCPP库的使用与原理解析
君子不器 🚀JsonCPP开源项目直达链接 文章目录 简介Json示例小结 JsoncppJson::Value序列化Json::Writer 类Json::FastWriter 类Json::StyledWriter 类Json::StreamWriter 类Json::StreamWriterBuilder 类示例 反序列化Json::Reader 类Json::CharReader 类Json::Ch…...
字节UC伯克利新研究 | Magic-Me:简单有效的主题ID可控视频生成框架
在生成模型领域,针对特定身份(ID)创建内容已经引起了极大的兴趣。在文本到图像生成(T2I)领域,以主题驱动的内容生成已经取得了巨大的进展,使图像中的ID可控。然而,将其扩展到视频生成…...
2024免费人像摄影后期处理工具Portraiture4.1
Portraiture作为一款智能磨皮插件,确实为Photoshop和Lightroom用户带来了极大的便利。通过其先进的人工智能算法,它能够自动识别并处理照片中的人物皮肤、头发和眉毛等部位,实现一键式的磨皮美化效果,极大地简化了后期处理的过程。…...
Spring Boot 笔记 010 创建接口_更新用户头像
1.1.1 usercontroller中添加updateAvatar,校验是否为url PatchMapping("updateAvatar")public Result updateAvatar(RequestParam URL String avatarUrl) {userService.updateAvatar(avatarUrl);return Result.success();} 1.1.2 userservice //更新头像…...
认识并使用HttpLoggingInterceptor
目录 一、前情回顾二、HttpLoggingInterceptor1、HttpLoggingInterceptor拦截器是做什么的?2、如何使用HttpLoggingInterceptor?2.1 日志级别2.2 如何看日志?2.2.1 日志级别:BODY2.2.2 日志级别:BASIC2.2.3 日志级别&a…...
内存块与内存池
(1)在运行过程中,MemoryPool内存池可能会有多个用来满足内存申请请求的内存块,这些内存块是从进程堆中开辟的一个较大的连续内存区域,它由一个MemoryBlock结构体和多个可供分配的内存单元组成,所有内存块组…...
【FPGA开发】HDMI通信协议解析及FPGA实现
本篇文章包含的内容 一、HDMI简介1.1 HDMI引脚解析1.2 HDMI工作原理1.3 DVI编码1.4 TMDS编码 二、并串转换、单端差分转换原语2.1 原语简介2.2 原语:IO端口组件2.3 IOB 输入输出缓冲区2.4 并转串原语OSERDESE22.4.1 OSERDESE2 工作原理2.4.2 OSERDESE2 级联示意图2.…...
[NSSRound#16 Basic]Web
1.RCE但是没有完全RCE 显示md5强比较,然后md5_3随便传 md5_1M%C9h%FF%0E%E3%5C%20%95r%D4w%7Br%15%87%D3o%A7%B2%1B%DCV%B7J%3D%C0x%3E%7B%95%18%AF%BF%A2%00%A8%28K%F3n%8EKU%B3_Bu%93%D8Igm%A0%D1U%5D%83%60%FB_%07%FE%A2&md5_2M%C9h%FF%0E%E3%5C%20%95r%D4w…...
[职场] 会计学专业学什么 #其他#知识分享#职场发展
会计学专业学什么 会计学专业属于工商管理学科下的一个二级学科,本专业培养具备财务、管理、经济、法律等方面的知识和能力,具有分析和解决财务、金融问题的基本能力,能在企、事业单位及政府部门从事会计实务以及教学、科研方面工作的工商管…...
docker (五)-docker存储-数据持久化
将数据存储在容器中,一旦容器被删除,数据也会被删除。同时也会使容器变得越来越大,不方便恢复和迁移。 将数据存储到容器之外,这样删除容器也不会丢失数据。一旦容器故障,我们可以重新创建一个容器,将数据挂…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
