每日一题(LeetCode)----链表--链表中的下一个更大节点

每日一题(LeetCode)----链表–链表中的下一个更大节点

1.题目(1019. 链表中的下一个更大节点)

    • 给定一个长度为 n 的链表 head

      对于列表中的每个节点,查找下一个 更大节点 的值。也就是说,对于每个节点,找到它旁边的第一个节点的值,这个节点的值 严格大于 它的值。

      返回一个整数数组 answer ,其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点,设置 answer[i] = 0

      示例 1:

      img

      输入:head = [2,1,5]
      输出:[5,5,0]
      

      示例 2:

      img

      输入:head = [2,7,4,3,5]
      输出:[7,0,5,5,0]
      

      提示:

      • 链表中节点数为 n
      • 1 <= n <= 104
      • 1 <= Node.val <= 109

2.解题思路

思路一:使用单调栈

1.我们创建一个单调栈(递减栈),这个栈中存的元素是pair类型的,pair的第一个变量存的是遍历到节点的下标,第二个变量存的是遍历到的节点的值
2.遍历链表,我们每遍历到一个节点,先把当前位置看成是零,放入到一个数组(这里我们用的是动态数组)中,然后看栈中是否有元素
如果栈中有元素,看栈顶元素的值是否小于当前节点的值
如果小于,那么我们通过当前栈顶元素的第二个变量,找到数组应该修改的那个元素的下标,然后那个元素修改为当前节点的值,将当前栈顶元素删除,再重新看栈顶元素与当前元素的关系进行操作,当然如果栈中没有元素了,就不进行操作了。继续接下来的操作
如果大于,就继续接下来的操作(这是一个递减栈,如果栈顶元素都大于当前节点的的值了,那栈中其他元素也一定大于当前节点的值了)
如果栈中没有元素,继续接下来的操作
3.最后将当前节点的下标和当前节点的值作为一个整体放到栈中,继续遍历链表的下一个节点
4.遍历完链表之后,得到的数组就是我们的最终答案

3.写出代码

思路一的代码
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> ans;
        //pair的第一个变量存的是遍历到节点的下标,第二个变量存的是遍历到的节点的值
        stack<pair<int,int>> sta;
        int index=-1;
        ListNode* cur=head;
        while(cur){
            ans.push_back(0);
            index++;
            while(!sta.empty()&&sta.top().second<cur->val){
                ans[sta.top().first]=cur->val;
                sta.pop();
            }
            sta.push(make_pair(index,cur->val));
            cur=cur->next;
        }
        return ans;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/188360.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于单片机压力传感器MPX4115检测-报警系统proteus仿真+源程序

一、系统方案 1、本设计采用这51单片机作为主控器。 2、MPX4115采集压力值、DS18B20采集温度值送到液晶1602显示。 3、按键设置报警值。 4、蜂鸣器报警。 二、硬件设计 原理图如下&#xff1a; 三、单片机软件设计 1、首先是系统初始化 /*********************************…

【小沐学写作】原型设计工具汇总(Axure RP)

文章目录 1、简介2、Axure RP2.1 工具简介2.2 工具特点2.2.1 互动事件2.2.2 条件逻辑2.2.4 工作表格2.2.5 多状态容器2.2.6 数据驱动接口2.2.7 自适应视图2.2.8 流程图 2.3 工具安装2.3.1 安装2.3.2 运行 2.4 使用费用2.5 工具体验2.5.1 登陆框制作 3、其他3.1 Figma3.2 Adobe …

原生JS实现计算器(内含源码)

前言 本文讲解了JavaScript如何在一小时内实现一个简易计算器&#xff0c;这里最大的亮点就在于&#xff0c;我在JS中只用了一个事件&#xff0c;就实现了计算器的效果和功能&#xff0c;那么好文本正式开始。 布局和样式流程 首先是HTMLCSS结构&#xff1a;这里主要用到的…

c语言-字符函数和字符串函数详解

文章目录 1. 字符分类函数2. 字符转换函数3. strlen的使用和模拟实现4. strcpy的使用和模拟实现5. strncpy函数的使用6. strcat的使用和模拟实现7. strncat函数的使用8. strcmp的使用和模拟实现9. strncmp函数的使用10. strstr的使用和模拟实现11. strtok函数的使用12. strerro…

CTA-GAN:基于生成对抗性网络的主动脉和颈动脉非集中CT血管造影 CT到增强CT的合成技术

Generative Adversarial Network–based Noncontrast CT Angiography for Aorta and Carotid Arteries 基于生成对抗性网络的主动脉和颈动脉非集中CT血管造影背景贡献实验方法损失函数Thinking 基于生成对抗性网络的主动脉和颈动脉非集中CT血管造影 https://github.com/ying-f…

4-20mA高精度采集方案

下载链接&#xff01;https://mp.weixin.qq.com/s?__bizMzU2OTc4ODA4OA&mid2247557466&idx1&snb5a323285c2629a41d2a896764db27eb&chksmfcfaf28dcb8d7b9bb6211030d9bda53db63ab51f765b4165d9fa630e54301f0406efdabff0fb&token976581939&langzh_CN#rd …

kafka精准一次、事务、幂等性

Kafka事务 消息中间件的消息保障的3个级别 At most once 至多一次。数据丢失。At last once 至少一次。数据冗余Exactly one 精准一次。好&#xff01;&#xff01;&#xff01; 如何区分只要盯准提交位移、消费消息这两个动作的时机就可以了。 当&#xff1a;先消费消息、…

计算机中由于找不到vcruntime140.dll无法继续执行代码无法打开软件怎么解决分享

关于如何解决vcruntime140.dll无法继续执行代码的6个教程。在这个科技日新月异的时代&#xff0c;电脑已经是我们日常和工作中必不可少的电子产品&#xff0c;然后我们在使用过程中经常会遇到不一样的问题&#xff0c;比如vcruntime140.dll文件丢失&#xff0c;那么vcruntime14…

selenium的基础语法

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️山水速疾来去易&#xff0c;襄樊镇固永难开 ☁️定位页面的元素 参数:抽象类By里…

实验题【网关设置+VRRP+OSPF】(H3C模拟器)

嘿&#xff0c;这里是目录&#xff01; ⭐ H3C模拟器资源链接1. 实验示意图2. 要求和考核目标3. 当前配置3.1 PC1、PC2、PC3、PC4和PC5配置3.2 SW配置3.2.1 SW2配置3.2.2 SW3配置3.2.3 SW4配置3.2.4 SW1配置 3.2. R配置3.2.1 R1配置3.2.2 R2配置 ⭐ H3C模拟器资源链接 H3C网络…

Cesium-terrain-builder编译入坑详解

本以为编译cesium-terrian-tools编译应该没那么难&#xff0c;不想问题重重&#xff0c;不想后人重蹈覆辙&#xff0c;也记录下点点滴滴。 目前网上存在的cesium代码版本主要有两个分支&#xff1a; 原始网站【不能生成layer文件&#xff0c;且经久不更新&#xff0c;使用gdal…

计算机应用基础_错题集_PPT演示文稿_操作题_计算机多媒体技术操作题_文字处理操作题---网络教育统考工作笔记007

PPT演示文稿操作题 提示:PPT部分操作题 将第2~第4张幻灯片背景效果设为渐变预置的“雨后初晴”效果(2)设置幻灯片放映方式

【小沐学写作】免费在线AI辅助写作汇总

文章目录 1、简介2、文涌Effidit&#xff08;腾讯&#xff09;2.1 工具简介2.2 工具功能2.3 工具体验 3、PPT小助手&#xff08;officeplus&#xff09;3.1 工具简介3.2 使用费用3.3 工具体验 4、DeepL Write&#xff08;仅英文&#xff09;4.1 工具简介4.2 工具体验 5、天工AI…

【负载均衡】这些内容你需要知道下

&#x1f604;作者简介&#xff1a; 小曾同学.com,一个致力于测试开发的博主⛽️&#xff0c;主要职责&#xff1a;测试开发、CI/CD 如果文章知识点有错误的地方&#xff0c;还请大家指正&#xff0c;让我们一起学习&#xff0c;一起进步。 &#x1f60a; 座右铭&#xff1a;不…

Golang并发模型:Goroutine 与 Channel 初探

文章目录 goroutinegoexit() channel缓冲closerangeselect goroutine goroutine 是 Go 语言中的一种轻量级线程&#xff08;lightweight thread&#xff09;&#xff0c;由 Go 运行时环境管理。与传统的线程相比&#xff0c;goroutine 的创建和销毁的开销很小&#xff0c;可以…

Python基于jieba+wordcloud实现文本分词、词频统计、条形图绘制及不同主题的词云图绘制

目录 序言&#xff1a;第三方库及所需材料函数模块介绍分词词频统计条形图绘制词云绘制主函数 效果预览全部代码 序言&#xff1a;第三方库及所需材料 编程语言&#xff1a;Python3.9。 编程环境&#xff1a;Anaconda3&#xff0c;Spyder5。 使用到的主要第三方库&#xff1a;…

【Leetcode】【实现循环队列】【数据结构】

代码实现&#xff1a; typedef struct {int front;int back;int k;int* a;} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->frontobj->back; }bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back1)%(obj->…

位图和布隆过滤器

目录 一. 位图 1.题目&#xff1a; 给40亿个不重复的无符号整数&#xff0c;没排过序。给一个无符号整数&#xff0c;如何快速判断一个数是否在这40亿个数中&#xff1f; 2.解析题目&#xff1a; 3.位图 4.代码以及测试 5.其他题目 二.布隆过滤器 1.介绍 2.实现 …

Vue服务端渲染——同构渲染

Vue.js 可以用于构建客户端应用程序&#xff0c;组件的代码在浏览器中运行&#xff0c;并输出 DOM 元素。同时&#xff0c;Vue.js 还可以在 Node.js 环境中运行&#xff0c;它可以将同样的组件渲染为字符串并发送给浏览器。这实际上描述了 Vue.js 的两种渲染方式&#xff0c;即…

【云原生】什么是 Kubernetes ?

什么是 Kubernetes &#xff1f; Kubernetes 是一个开源容器编排平台&#xff0c;管理着一系列的 主机 或者 服务器&#xff0c;它们被称作是 节点&#xff08;Node&#xff09;。 每一个节点运行了若干个相互独立的 Pod。 Pod 是 Kubernetes 中可以部署的 最小执行单元&#x…
最新文章