leetcode496. 下一个更大元素 I 【单调栈】
【简单题】(暴力遍历法很简单)但是时间复杂度很高,n的立方级别了。。。
代码:
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> ans; // 存放结果for (int i = 0; i < nums1.size(); i++) {int t = nums1[i]; // 暂存要查找的值for (int j = 0; j < nums2.size(); j++) { // 在nums2中找与t相等的值if (nums2[j] == t) { // 如果找到相等的值,就往后找第一个比他大的int k;for (k = j + 1; k < nums2.size(); k++) {if (nums2[k] > t) { // 找到第一个比它大的元素,压入该元素入栈ans.push_back(nums2[k]);break;}}if (k == nums2.size()) { // 遍历完nums2数组,没有找到比它大的元素。压入 -1 入栈ans.push_back(-1);}}}}return ans;}
};
运行结果:
进阶方法:
进阶:你可以设计一个时间复杂度为 O(nums1.length + nums2.length)
的解决方案吗?
答案思路:【单调栈】
怎么样才能使得 用 nums1中的元素去 nums2中查找的时候,能够很快的不用遍历就可以查到第一个比它大的元素呢?
先预处理 num2,使得对于他的每个元素,用一个哈希表来存储第一个比他大的元素的映射。
步骤(参考leetcode官方题解)
遍历完之后 hashmap 中存储的键值对如下所示:
自己的话总结:
从后往前遍历(当前值为t),如果栈中的值比 t 小,则出栈到没有比它小 或 栈空位置。然后设置哈希映射,键为 t,值为 栈顶元素。然后将该元素入栈。直到遍历完第一个元素。
这样,对于 nums2中的每一个元素,在hashmap中都存储了 第一个比他大的元素 的映射。
注意:
使用 unordered_map 时,要引入库文件:#include <unordered_map>
代码:
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> mp; // 设置哈希表stack<int> st; // 栈for (int i = nums2.size() - 1; i >= 0; i--) { // 从后往前遍历 nums2int t = nums2[i];while (!st.empty() && t > st.top()) // 如果栈非空的条件下,当前值 > 栈顶元素,就出栈st.pop();if (st.empty()) { // 如果栈为空,说明在该数组中,该元素没有第一个比它大的元素,设置它的映射值为 -1mp[t] = -1;}else {mp[t] = st.top(); // 如果栈非空,那么该元素的哈希映射值为 栈顶元素。}st.push(t); }vector<int> ans;for (int i = 0; i < nums1.size(); i++) {ans.push_back(mp[nums1[i]]);}return ans;}
};
相关文章:
leetcode496. 下一个更大元素 I 【单调栈】
【简单题】(暴力遍历法很简单)但是时间复杂度很高,n的立方级别了。。。 代码: class Solution { public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int&g…...
Fastadmin框架 聚合数字生活抵扣卡系统v2.8.6
【2.8.6更新公告】 1.【优化】优化已知问题。 2.【新增 】新增区县影院。...
windows下MSYS、MinGW编译环境使用网络API时报错:undefined reference to `inet_pton‘解决办法
windows下MSYS、MinGW编译环境使用网络API时报错:undefined reference to inet_pton’解决办法 mingw-gcc环境使用网络需要加上库 -lws2_32。 如果是使用的是Qt Creator那么需要在.pro文件中加入一行:win32:LIBS -lws2_32。 当在项目中使用inet_pton、…...
unity-AI自动导航
unity-AI自动导航 给人物导航 一.地形创建 1.首先我们在Hierarchy面板中创建一个地形对象terrian,自行设定地形外貌,此时我们设置一个如下的地形外观。 二.创建导航系统 1.在主人公的Inspector、面板中添加Nav Mesh Agent (导航网格代理&…...
使用create-react-app创建react项目
create-react-app 全局安装create-react-app npm install -g create-react-app 使用create-react-app创建一个项目 $ create-react-app your-app 注意命名方式Creating a new React app in /dir/your-app.Installing packages. This might take a couple of minutes. 安装过…...
12.串,串的存储结构与模式匹配算法
目录 一. 一些术语 二. 串的类型定义 (1)串的顺序存储结构 (2)串的链式存储结构 三. 串的模式匹配算法 (1)BF算法 (2)KMP算法 四. 案例实现 串(String)---零个或多个任意字符…...
Ribbon:listOfServers ,${variableName:defaultValue}
解释: 配置了address的地址,请求会走address,也就是http://127.0.0.1:8081,通常用户与别的后端服务进行联调设置为其本地服务的ip。 如果address的地址被注释掉,如下面所示,类似这样的占位符${variableName:defaultVa…...
TensorFlow二元-多类-多标签分类示例
探索不同类型的分类模型,使用 TensorFlow 构建二元、多类和多标签分类器。 二元分类 简述 逻辑回归 二元交叉熵 二元分类架构 案例:逻辑回归预测获胜团队 多类分类 简述 Softmax 函数 分类交叉熵 多类分类架构 案例:预测航天飞机…...
【回眸】牛客网刷刷刷!(七)——通信协议之 网络通讯
目录 前言 1、TCP/IP分层模型 2、ARP缓存 3、TCP 协议之所以提供可靠传输,不怕丢包、乱序的主要的原因是 4、以太网数据链路层MII/GMII/RMII/RGMII四种常用接口 5、在以太网通信协议LWIP中,数据包管理机构采用数据结构pbuf 分类包括 6、关于以太网…...
MySQL 安装配置
MySQL 安装配置 MySQL 是最流行的关系型数据库管理系统,由瑞典MySQL AB公司开发,目前属于Oracle公司。 MySQL所使用的SQL语言是用于访问数据库的最常用标准化语言。 MySQL由于其体积小、速度快、总体拥有成本低,尤其是开放源码这一特点,一般中小型网站的开发都选择MySQL…...
【0824作业】C++ 拷贝赋值函数、匿名对象、友元、常成员函数和常对象、运算符重载
一、思维导图 二、作业:实现关系运算符的重载 关系运算符重载 概念: 种类:>、>、< 、< 、 、!表达式:L#R (L表示左操作数,R表示有操作数,#表示运算符)左操作数:既可以是左值也可以…...
ubuntu 22.04 LTS openai triton 安装
第一种方法: pip install triton 第二种方法,安装最新的版本: pip install -U --index-url https://aiinfra.pkgs.visualstudio.com/PublicPackages/_packaging/Triton-Nightly/pypi/simple/ triton-nightly 第三种方法: git c…...
Android SDK 上手指南||第七章 Java应用程序编程
第七章 Java应用程序编程 如果大家已经对Java非常熟悉,那么不妨直接忽略这部分内容。如果大家的技巧还存在局限或者对Java这种语言只闻其名,那么本文将为各位解答很多在Android开发当中经常遇到的问题。需要注意的是,这篇文章并不能作为Java…...
Vue 框架如何获取数组中的值?
在Vue框架中,获取数组中的值可以通过以下几种方式实现: 1、使用数组索引: 可以使用数组的索引来获取特定位置的值。在Vue中,可以通过在模板中使用差值表达式或指令来获取数组中的值。例如: <div>{{ myArray[0]…...
如何成立一家音频芯片/算法设计公司
一 如何成立一家音频芯片设计公司? 要成立一家音频芯片设计公司,可以按照以下步骤进行: 市场调研:了解音频芯片市场的需求和竞争情况,确定目标客户和定位。 制定商业计划:根据市场调研的结果࿰…...
用docker-compose搭建LNMP
docker-compose搭建LNMP 一、compose 的部署1.Docker Compose 环境安装 二、编写Docker Compose1.准备依赖文件,配置nginx2.配置mysql3.配置php4.编写docker-compose.yml5.执行6.查看 一、compose 的部署 (1)公司在实际的生产环境中,需要使用…...
JavaScript:基本语法(变量与函数的定义与使用)
文章目录 script 标签srcdefer 延迟加载 基本语法定义变量 与 使用变量基本类型typeof 查看变量类型复合类型数组类型定义对象类型定义 函数定义函数使用函数 script 标签 src 和scc一样可以内嵌也可以外src外引。 一般是推荐外引。 <script src"idx.js">&l…...
树莓派4B上安装Gitlab
参考连接: 树莓派上使用 GitLab 搭建专业 Git 服务 | 树莓派实验室 gitlab reconfigure 卡住 ruby_block[wait for redis service socket] action run_芹菜学长的博客-CSDN博客 以及用到了讯飞星火 系统版本信息 1.进入 giblab安装页面gitlab/gitlab-ce - Instal…...
JVM 之字节码(.class)文件
本文中的内容参考B站尚硅谷宋红康JVM全套教程 你将获得: 1、掌握字节码文件的结构 2、掌握Java源代码如何在JVM中执行 3、掌握一些虚拟机指令 4、回答一些面试题 课程介绍 通过几个面试题初始字节码文件为什么学习class字节码文件什么是class字节码文件分析c…...
neo4j函数
1、断言函数 1all()判断是否一个断言适用于列表中的所有元素2all()判断是否一个断言至少适用于列表中的一个元素3none()如果断言不适用于列表中的任何元素,则返回true4single()如果断言刚好只适用于列表中的某一个元素,则返回true5exists()如果数据局库…...
wazuh初探系列一 : wazuh环境配置
目录 方法一:一体化部署 安装先决条件 第一步、安装所有必需的软件包 第二步、安装Elasticsearch 1、添加 Elastic Stack 存储库 安装 GPG 密钥: 添加存储库: 更新源: 2、Elasticsearch安装和配置 安装 Elasticsearch 包…...
【2023】Spring Validation中@NotNull注解、@NotBlank注解介绍以及使用
【2023】Spring Validation中NotNull注解、NotBlank注解介绍以及使用 前言一、简介spring-validation框架的常用注解 二、代码实现添加依赖1、实体举例2、Controller层:3、统一异常处理4、结果返回验证通过返回验证失败返回 前言 平常我们在编写代码的时候总需要很多if判空&am…...
nodejs+vue养老院管理系统 u1yrv
本智慧养老中心管理系统是为了提高用户查阅信息的效率和管理人员管理信息的工作效率,可以快速存储大量数据,还有信息检索功能,这大大的满足了老人信息和管理员这两者的需求。操作简单易懂,合理分析各个模块的功能,尽可…...
高效PDF校对:释放高质量内容的力量
在数字化世界中,内容是王者。随着企业和个人越来越依赖数字文档进行沟通、分享和创新,我们在PDF中传递的内容的质量变得至关重要。在这里,我们将探索高效的PDF校对如何帮助您释放高质量内容的真正潜力。 超越仅仅是“正确” 当我们谈论PDF校…...
【Git游戏】提交的技巧
修改历史的提交 rebase 通过git rebase -i 将要修改的提交提到最前端, 然后修改,再通过git commit --amend提交该记录,最后通过git rebase -i 在替换会原始的位置 (该过程中有可能会产生rebase confict) cherry-pick …...
SQL注入读写文件
文章目录 条件利用SQL注入漏洞读取hosts文件查看文件读写权限安全选项允许导入导出读取hosts文件 利用SQL注入漏洞写入一句话木马,并用蚁剑连接webshell写入文件 条件 SQL注入有直接SQL注入,也有文件读写时的注入,后者的主要 目的在于获取web…...
stm32之12.如何使用printf打印输出
主函数增加这些代码即可实现printf打印输出 需要添加头文件 #include "stdio.h" --------------- 源码 struct __FILE { int handle; /* Add whatever you need here */ }; FILE __stdout; FILE __stdin; int fputc(int c, FILE *f) { /* 发送一个字节 */ …...
敏感挂载hotplug容器逃逸分析与复现
前言 分析 实验 echo /path/to/hotplug/script > /proc/sys/kernel/hotplug 直接挂载设备即可,虚拟机直接启动或者卸载一下声卡就行 参考 Linux uevent分析、用户接收uevent以及mdev分析 - ArnoldLu - 博客园 (cnblogs.com)...
RTThread学习有关的Keil的两个符号 $Sub$ $main 与 $Super$ $main
Keil的两个符号$Sub$ $与 $Super$ $是其做的打“补丁”功能 具体调用方法就是程序中包含有main函数,和 $Sub$ $main 、 $Super$ $main 两个符号 源码先放出来 /* re-define main function */ int $Sub$$main(void) {rtthread_startup();return 0; }/*** brief Thi…...
Python实现企业微信群告警
Python实现企业微信告警 1. 创建企业微信群机器人 1-1. 什么是企业微信群机器人? 企业微信群机器人是企业微信平台提供的一种功能,可以通过Webhook方式将消息发送到指定的企业微信群中。它可以用于自动化发送通知、告警等信息,实现监控和信…...
python基础教程:re模块用法详解
前言 嗨喽,大家好呀~这里是爱看美女的茜茜呐 一、正则表达式的特殊字符介绍 正则表达式 👇 👇 👇 更多精彩机密、教程,尽在下方,赶紧点击了解吧~ 素材、视频教程、完整代码、插件安装教程我都准备好了&a…...
基于亚马逊云科技无服务器服务快速搭建电商平台——部署篇
受疫情影响消费者习惯发生改变,刺激了全球电商行业的快速发展。除了依托第三方电商平台将产品销售给消费者之外,企业通过品牌官网或者自有电商平台销售商品也是近几年电商领域快速发展的商业模式。独立站电商模式可以进行多方面、全渠道的互联网市场拓展…...
git介绍+集成到IDEA中+使用gitee
目录 git介绍 本地工作流程 IDEA集git 添加到暂存区 添加到本地仓库 gitee使用 添加到远程仓库 git介绍 git是一个开源的分布式版本控制工具,效率高。可以记录历史代码,多人代码共享 知识小点: 集中式版本控制:使用中央存…...
【java】【项目实战】[外卖四]分类管理业务开发
前言:公共字段自动填充实现,删除业务逻辑实现 一、公共字段自动填充 1.1 问题分析 1.2 代码实现 1.2.1 修改实体类Employee package com.runa.reggie.entity;import com.baomidou.mybatisplus.annotation.FieldFill; import com.baomidou.mybatisplus.…...
【Go 基础篇】Go语言包详解:模块化开发与代码复用
介绍 在Go语言中,包(Package) 是一种用于组织代码的机制,用于将相关的函数、类型和变量等组织在一起,以便于模块化开发和代码复用。包的使用能够使程序结构更加清晰、可维护性更高,同时也是Go语言强调的一…...
【业务功能篇82】微服务SpringCloud-ElasticSearch-Kibanan-docke安装-进阶实战
四、ElasticSearch进阶 https://www.elastic.co/guide/en/elasticsearch/reference/7.4/getting-started-search.html 1.ES中的检索方式 在ElasticSearch中支持两种检索方式 通过使用REST request URL 发送检索参数(uri检索参数)通过使用 REST request body 来发送检索参数…...
【工具】XML和JSON互相转换
1、JSON解析为XML function parseJSONToXML(json) {let xmlDoc document.implementation.createDocument(null, );function parseValue(value, parentElement) {if (Array.isArray(value)) {for (let item of value) {let arrayElement xmlDoc.createElement(parentElement.…...
前端面试:【浏览器与渲染引擎】Web APIs - DOM、XHR、Fetch、Canvas
嗨,亲爱的读者!当我们在浏览器中浏览网页时,我们常常会与各种Web API打交道。这些API允许我们与网页内容、服务器资源和图形进行交互。本文将深入探讨一些常见的Web API,包括DOM、XHR、Fetch和Canvas,以帮助你了解它们…...
编码基础一:侵入式链表
一、简介概述 1、普通链表数据结构 每个节点的next指针指向下一个节点的首地址。这样会有如下的限制: 一条链表上的所有节点的数据类型需要完全一致。对某条链表的操作如插入,删除等只能对这种类型的链表进行操作,如果链表的类型换了&#…...
深圳IT行业供需:蓬勃发展的科技中心
深圳作为中国的科技中心之一,IT行业在这座城市蓬勃发展。本文将探讨深圳IT行业的供需状况,包括就业机会、技能需求以及行业前景展望。 近年来,深圳IT行业迅速发展,成为全球科技创新的重要枢纽之一。随着大量的科技企业和初创公司在…...
LeetCode 面试题 02.01. 移除重复节点
文章目录 一、题目二、C# 题解 一、题目 编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。 点击此处跳转题目。 示例1: 输入:[1, 2, 3, 3, 2, 1] 输出:[1, 2, 3] 示例2: 输入:[1, 1, 1, 1, 2] 输出:[1, …...
【Java8特性】——Stream API
一、概述 <1> 是什么 是数据渠道,用于操作数据源(集合、数组等)所生成的元素序列。 Stream 不会存储数据Stream 不会改变数据源,相反,会返回一个持有结果的新Stream。Stream 操作是延迟执行的,这意…...
grep命令的用法
文章目录 前言一、使用说明二、应用举例 前言 grep 命令用于查找文件里符合条件的字符串。 一、使用说明 -r: 如果需要搜索目录中的文件内容, 需要进行递归操作, 必须指定该参数 -i: 对应要搜索的关键字, 忽略字符大小写的差别 -n: 在显示符合样式的那一行之前,标…...
【无标题】jenkins消息模板(飞书)
这里写目录标题 Jenkins 安装的插件 发送消息到飞书预览 1 (单Job)预览 2 (多Job,概览) Jenkins 安装的插件 插件名称作用Rebuilder Rebuilder。 官方地址:https://plugins.jenkins.io/rebuild 安装方式&a…...
2023年国赛 高教社杯数学建模思路 - 案例:随机森林
文章目录 1 什么是随机森林?2 随机深林构造流程3 随机森林的优缺点3.1 优点3.2 缺点 4 随机深林算法实现 建模资料 ## 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 什么是随机森林ÿ…...
element Collapse 折叠面板 绑定事件
1. 点击面板触发事件 change <el-collapse accordion v-model"activeNames" change"handleChange"><el-collapse-item title"一致性 Consistency"><div>与现实生活一致:与现实生活的流程、逻辑保持一致,…...
CSS :mix-blend-mode、aspect-ratio
mix-blend-mode 元素的内容应该与元素的直系父元素的内容和元素的背景如何混合。 mix-blend-mode: normal; // 正常mix-blend-mode: multiply; // 正片叠底mix-blend-mode: screen; // 滤色mix-blend-mode: overlay; // 叠加mix-blend-mode: darken; // 变暗mix-blend-mode: …...
Module not found: Error: Can‘t resolve ‘less-loader‘解决办法
前言: 主要是在自我提升方面,感觉自己做后端还是需要继续努力,争取炮筒前后端,作为一个全栈软阿金开发人员,所以还是需要努力下,找个方面,目前是计划学会Vue,这样后端有java和pytho…...
量化QAT QLoRA GPTQ
模型量化的思路可以分为PTQ(Post-Training Quantization,训练后量化)和QAT(Quantization Aware Training,在量化过程中进行梯度反传更新权重,例如QLoRA),GPTQ是一种PTQ的思路。 QAT…...
CentOS下查看 ssd 寿命
SSD写入量达到设计极限,颗粒擦写寿命耗尽后会导致磁盘写入速度非常缓慢,读取正常。 使用smartctl及raid卡管理软件查看硬盘smart信息可以发现Media_Wearout_Indicator值降为1,表明寿命完全耗尽。 涉及范围 所有SSD处理方案 查看SSD smart信…...