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

【算法与数据结构】496、503、LeetCode下一个更大元素I II

文章目录

  • 一、496、下一个更大元素 I
  • 二、503、下一个更大元素II
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、496、下一个更大元素 I

在这里插入图片描述

  思路分析:本题思路和【算法与数据结构】739、LeetCode每日温度类似。如果用暴力破解法时间复杂度需要 O ( m ∗ n ) O(m*n) O(mn),其中 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题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、496、下一个更大元素 I 思路分析&#xff1a;本题思路和【算法与数据结构】739、LeetCode每日温度类似…...

当AGI遇到人形机器人

为什么人类对人形机器人抱有执念 人形机器人是一种模仿人类外形和行为的机器人&#xff0c;它的研究和开发有着多方面的目的和意义。 人形机器人可以更好地适应人类的环境和工具。人类的生活和工作空间都是根据人的尺寸和动作来设计的&#xff0c;例如门、楼梯、桌椅、开关等…...

Pytorch卷积层原理和示例 nn.Conv1d卷积 nn.Conv2d卷积

内容列表 一&#xff0c;前提 二&#xff0c;卷积层原理 1.概念 2.作用 3. 卷积过程 三&#xff0c;nn.conv1d 1&#xff0c;函数定义&#xff1a; 2, 参数说明: 3,代码: 4, 分析计算过程 四&#xff0c;nn.conv2d 1, 函数定义 2, 参数&#xff1a; 3, 代码 4, 分析计算过程 …...

Qt 实现无边框窗口1.0

目录 项目需求&#xff1a; 1、没有边框&#xff1b; 2、点击windows系统的状态栏的程序运行图标可实现最大最小化&#xff1b; 3、可以移动窗口&#xff1b; 项目实现&#xff1a; 1、实现 无边框 2、实现 点击windows系统的状态栏的程序运行图标可实现最大最小化 3、实现 窗…...

Flume(二)【Flume 进阶使用】

前言 学数仓的时候发现 flume 落了一点&#xff0c;赶紧补齐。 1、Flume 事务 Source 在往 Channel 发送数据之前会开启一个 Put 事务&#xff1a; doPut&#xff1a;将批量数据写入临时缓冲区 putList&#xff08;当 source 中的数据达到 batchsize 或者 超过特定的时间就会…...

静态时序分析:SDC约束命令set_clock_transition详解

相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 在静态时序分析&#xff1a;SDC约束命令create_clock详解一文的最后&#xff0c;我们谈到了针对理想(ideal)时钟&#xff0c;可以使用set_clock_transition命令直…...

web 发展阶段 -- 详解

1. web 发展阶段 当前处于 移动 web 应用阶段。也是个风口&#xff08;当然是针对有能力创业的人来说的&#xff09;&#xff0c;如 抖音、快手就是这个时代的产物。 2. web 发展阶段引出前后端分离的过程 2.1 传统开发方式 2.2 前后端分离模式 衍生自移动 web 应用阶段。 3.…...

车载软件架构 —— Adaptive AUTOSAR软件架构中操作系统

车载软件架构 —— Adaptive AUTOSAR软件架构中操作系统 我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师&#xff08;Wechat&#xff1a;gongkenan2013&#xff09;。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&…...

前缀和算法-截断数组

5057. 截断数组 - AcWing题库 给定一个长度为 n 的正整数数组 a1,a2,…,an 和一个正整数 p。 现在&#xff0c;要将该数组从中间截断&#xff0c;得到两个非空子数组。 我们规定&#xff0c;一个数组的价值等于数组内所有元素之和模 p 的结果。 我们希望&#xff0c;将给定数组…...

Kubernetes实战:Kubernetes中网络插件calico Daemon Sets显示异常红色

目录 一、排查步骤与解决方案1.1、POD排查问题定位1.2、针对问题解决错误1.3、继续针对问题解决错误 一、排查步骤与解决方案 1.1、POD排查问题定位 我的k8s集群由3个节点组成的&#xff0c;calico在每个节点上都有一个pod,通过kubectl get pod -A命令发现有一个pod的READY 为…...

深入探究:JSONCPP库的使用与原理解析

君子不器 &#x1f680;JsonCPP开源项目直达链接 文章目录 简介Json示例小结 JsoncppJson::Value序列化Json::Writer 类Json::FastWriter 类Json::StyledWriter 类Json::StreamWriter 类Json::StreamWriterBuilder 类示例 反序列化Json::Reader 类Json::CharReader 类Json::Ch…...

字节UC伯克利新研究 | Magic-Me:简单有效的主题ID可控视频生成框架

在生成模型领域&#xff0c;针对特定身份&#xff08;ID&#xff09;创建内容已经引起了极大的兴趣。在文本到图像生成&#xff08;T2I&#xff09;领域&#xff0c;以主题驱动的内容生成已经取得了巨大的进展&#xff0c;使图像中的ID可控。然而&#xff0c;将其扩展到视频生成…...

2024免费人像摄影后期处理工具Portraiture4.1

Portraiture作为一款智能磨皮插件&#xff0c;确实为Photoshop和Lightroom用户带来了极大的便利。通过其先进的人工智能算法&#xff0c;它能够自动识别并处理照片中的人物皮肤、头发和眉毛等部位&#xff0c;实现一键式的磨皮美化效果&#xff0c;极大地简化了后期处理的过程。…...

Spring Boot 笔记 010 创建接口_更新用户头像

1.1.1 usercontroller中添加updateAvatar&#xff0c;校验是否为url PatchMapping("updateAvatar")public Result updateAvatar(RequestParam URL String avatarUrl) {userService.updateAvatar(avatarUrl);return Result.success();} 1.1.2 userservice //更新头像…...

认识并使用HttpLoggingInterceptor

目录 一、前情回顾二、HttpLoggingInterceptor1、HttpLoggingInterceptor拦截器是做什么的&#xff1f;2、如何使用HttpLoggingInterceptor&#xff1f;2.1 日志级别2.2 如何看日志&#xff1f;2.2.1 日志级别&#xff1a;BODY2.2.2 日志级别&#xff1a;BASIC2.2.3 日志级别&a…...

内存块与内存池

&#xff08;1&#xff09;在运行过程中&#xff0c;MemoryPool内存池可能会有多个用来满足内存申请请求的内存块&#xff0c;这些内存块是从进程堆中开辟的一个较大的连续内存区域&#xff0c;它由一个MemoryBlock结构体和多个可供分配的内存单元组成&#xff0c;所有内存块组…...

【FPGA开发】HDMI通信协议解析及FPGA实现

本篇文章包含的内容 一、HDMI简介1.1 HDMI引脚解析1.2 HDMI工作原理1.3 DVI编码1.4 TMDS编码 二、并串转换、单端差分转换原语2.1 原语简介2.2 原语&#xff1a;IO端口组件2.3 IOB 输入输出缓冲区2.4 并转串原语OSERDESE22.4.1 OSERDESE2 工作原理2.4.2 OSERDESE2 级联示意图2.…...

[NSSRound#16 Basic]Web

1.RCE但是没有完全RCE 显示md5强比较&#xff0c;然后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…...

[职场] 会计学专业学什么 #其他#知识分享#职场发展

会计学专业学什么 会计学专业属于工商管理学科下的一个二级学科&#xff0c;本专业培养具备财务、管理、经济、法律等方面的知识和能力&#xff0c;具有分析和解决财务、金融问题的基本能力&#xff0c;能在企、事业单位及政府部门从事会计实务以及教学、科研方面工作的工商管…...

docker (五)-docker存储-数据持久化

将数据存储在容器中&#xff0c;一旦容器被删除&#xff0c;数据也会被删除。同时也会使容器变得越来越大&#xff0c;不方便恢复和迁移。 将数据存储到容器之外&#xff0c;这样删除容器也不会丢失数据。一旦容器故障&#xff0c;我们可以重新创建一个容器&#xff0c;将数据挂…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...