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

LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】

LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】

  • 题目描述:
  • 解题思路一:可以将链表转为数组,然后从后往前遍历,遇到大于等于当前元素的就入栈,最终栈里面的元素即是最终的答案。
  • 解题思路二:递归,思路是递归到最后,head后面是node,如果node的值大于head的值,那么删除head。否则不删除。
  • 解题思路三:迭代:两次反转链表
  • 解题思路四:单调栈不解释

题目描述:

给你一个链表的头节点 head 。

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head 。

示例 1:
在这里插入图片描述

输入:head = [5,2,13,3,8]
输出:[13,8]
解释:需要移除的节点是 5 ,2 和 3 。

  • 节点 13 在节点 5 右侧。
  • 节点 13 在节点 2 右侧。
  • 节点 8 在节点 3 右侧。

示例 2:
输入:head = [1,1,1,1]
输出:[1,1,1,1]
解释:每个节点的值都是 1 ,所以没有需要移除的节点。

提示:

给定列表中的节点数目在范围 [1, 105] 内
1 <= Node.val <= 105

解题思路一:可以将链表转为数组,然后从后往前遍历,遇到大于等于当前元素的就入栈,最终栈里面的元素即是最终的答案。

不过这种思路也许有些投机取巧,没有用到纯粹的链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:nums = []while head:nums.append(head.val)head = head.nextn = len(nums)stack = []for i in range(n-1, -1, -1):if not stack: stack.append(nums[i])continueif nums[i] >= stack[-1]: stack.append(nums[i])for i, num in enumerate(reversed(stack)):if i == 0:head = ListNode(num)p = headelse:q = ListNode(num)p.next = qp = qreturn head

时间复杂度:O(n) 只是遍历了两遍链表
空间复杂度:O(n) 存储的数组

解题思路二:递归,思路是递归到最后,head后面是node,如果node的值大于head的值,那么删除head。否则不删除。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:if head.next is None: return head  # 输入保证链表不为空node = self.removeNodes(head.next)  # 返回的链表头一定是最大的if node.val > head.val: return node  # 删除 headhead.next = node  # 不删除 headreturn head

简单的写法:

class Solution:def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head: return headhead.next = self.removeNodes(head.next)return head.next if head.next and head.val < head.next.val else head 

时间复杂度:O(n)其中 n 为链表的长度。
空间复杂度:O(n) 栈空间

解题思路三:迭代:两次反转链表

翻转链表看LeetCode-206. 反转链表【双指针,递归】这里用的是简单的双指针来翻转链表,然后遇到比当前元素小的就可以直接删除,然后再次翻转链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre, cur = None, headwhile cur:nxt = cur.nextcur.next = prepre = curcur = nxtreturn predef removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:cur = head = self.reverseList(head)while cur.next:if cur.val > cur.next.val: cur.next = cur.next.nextelse: cur = cur.nextreturn self.reverseList(head)

时间复杂度:O(n) 只是遍历了两遍链表
空间复杂度:O(1) 原地翻转

解题思路四:单调栈不解释

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:A = []while head:while A and A[-1].val < head.val: A.pop()if A: A[-1].next = headA.append(head)head = head.nextreturn A[0]

时间复杂度:O(n)
空间复杂度:O(1)

相关文章:

LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】

LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】 题目描述&#xff1a;解题思路一&#xff1a;可以将链表转为数组&#xff0c;然后从后往前遍历&#xff0c;遇到大于等于当前元素的就入栈&#xff0c;最终栈里面的元素即是最终的答案。解题思路二&#xff1a;递归&am…...

Redisson分布式锁原理分析

1.Redisson实现分布式锁 在分布式系统中&#xff0c;涉及到多个实例对同一资源加锁的情况&#xff0c;传统的synchronized、ReentrantLock等单进程加锁的API就不再适用&#xff0c;此时就需要使用分布式锁来保证多服务之间加锁的安全性。 常见的分布式锁的实现方式有&#xff…...

【Linux】:线程(二)互斥

互斥与同步 一.线程的局部存储二.线程的分离三.互斥1.一些概念2.上锁3.锁的原理4.死锁 一.线程的局部存储 例子 可以看到全局变量是所有线程共享的&#xff0c;如果我们想要每个线程都单独访问g_val怎么办呢&#xff1f;其实我们可以在它前面加上__thread修饰。 这就相当于把g…...

vscode报错Pylance client: couldn‘t create connection to server.

问题描述&#xff1a; 一打开vscode&#xff0c;右下角就弹报错&#xff0c;Pylance client: couldn’t create connection to server.&#xff0c;让我打开output&#xff0c;打开后似乎是在说连不上server 因为连不上server&#xff0c;所以我的python代码没法解析&#xff0…...

智能优化算法应用:基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.萤火虫算法4.实验参数设定5.算法结果6.参考文…...

MacOS多屏状态栏位置不固定,程序坞不小心跑到副屏

目录 方式一&#xff1a;通过系统设置方式二&#xff1a;鼠标切换 MacOS多屏状态栏位置不固定&#xff0c;程序坞不小心跑到副屏 方式一&#xff1a;通过系统设置 先切换到左边 再切换到底部 就能回到主屏了 方式二&#xff1a;鼠标切换 我的两个屏幕放置位置如下 鼠标在…...

Python:pipdeptree 语法介绍

相信大家在按照一些包的时候经常会碰到版本不兼容&#xff0c;但是又不知道版本之间的依赖关系&#xff0c;今天给大家介绍一个工具&#xff1a;pipdeptree pipdeptree 是一个 Python 包&#xff0c;用于查看已安装的 pip 包及其依赖关系。它以树形结构展示包之间的依赖关系&am…...

【问题处理】—— lombok 的 @Data 大小写区分不敏感

问题描述 今天在项目本地编译的时候&#xff0c;发现有个很奇怪的问题&#xff0c;一直提示某位置找不到符号&#xff0c; 但是实际在Idea中显示确实正常的&#xff0c;一开始以为又是IDEA的故障&#xff0c;所以重启了IDEA&#xff0c;并执行了mvn clean然后重新编译。但是问…...

跟着我学Python基础篇:08.集合和字典

往期文章 跟着我学Python基础篇&#xff1a;01.初露端倪 跟着我学Python基础篇&#xff1a;02.数字与字符串编程 跟着我学Python基础篇&#xff1a;03.选择结构 跟着我学Python基础篇&#xff1a;04.循环 跟着我学Python基础篇&#xff1a;05.函数 跟着我学Python基础篇&#…...

Tomcat部署(图片和HTML等)静态资源时遇到的问题

文章目录 Tomcat部署静态资源问题图中HTML代码启动Tomcat后先确认Tomcat是否启动成功 Tomcat部署静态资源问题 今天&#xff0c;有人突然跟我提到&#xff0c;使用nginx部署静态资源&#xff0c;如图片。可以直接通过url地址访问&#xff0c;为什么他的Tomcat不能通过这样的方…...

在接触新的游戏引擎的时候,如何能快速地熟悉并开发出一款新游戏?

引言 大家好&#xff0c;今天分享点个人经验。 有一定编程经验或者游戏开发经验的小伙伴&#xff0c;在接触新的游戏引擎的时候&#xff0c;如何能快速地熟悉并开发出一款新游戏&#xff1f; 利用现成开发框架。 1.什么是开发框架&#xff1f; 开发框架&#xff0c;顾名思…...

计网 - TCP四次挥手原理全曝光:深度解析与实战演示

文章目录 Pre导图过程分析抓包实战第一次挥手 【FIN ACK】第二次挥手 【ACK】第三次挥手 【FINACK】第四次挥手 【ACK】 小结 Pre 计网 - 传输层协议 TCP&#xff1a;TCP 为什么握手是 3 次、挥手是 4 次&#xff1f; 计网 - TCP三次握手原理全曝光&#xff1a;深度解析与实战…...

个人养老金知多少?

个人养老金政策你了解吗&#xff1f;税优政策你知道吗&#xff1f;你会计算能退多少税吗&#xff1f;… 点这里看一看...

gpt3、gpt2与gpt1区别

参考&#xff1a;深度学习&#xff1a;GPT1、GPT2、GPT-3_HanZee的博客-CSDN博客 Zero-shot Learning / One-shot Learning-CSDN博客 Zero-shot&#xff08;零次学习&#xff09;简介-CSDN博客 GPT1、GPT2、GPT3、InstructGPT-CSDN博客 目录 gpt2与gpt1区别&#xff1a; gp…...

PyQt6 QDateEdit日期控件

​锋哥原创的PyQt6视频教程&#xff1a; 2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计39条视频&#xff0c;包括&#xff1a;2024版 PyQt6 Python桌面开发 视频教程(无废话…...

【无线网络技术】——无线城域网(学习笔记)

&#x1f4d6; 前言&#xff1a;无线城域网&#xff08;WMAN&#xff09;是指在地域上覆盖城市及其郊区范围的分布节点之间传输信息的本地分配无线网络。能实现语音、数据、图像、多媒体、IP等多业务的接入服务。其覆盖范围的典型值为3~5km&#xff0c;点到点链路的覆盖可以高达…...

RK3568平台 OTA升级原理

一.前言 在迅速变化和发展的物联网市场&#xff0c;新的产品需求不断涌现&#xff0c;因此对于智能硬件设备的更新需求就变得空前高涨&#xff0c;设备不再像传统设备一样一经出售就不再变更。为了快速响应市场需求&#xff0c;一个技术变得极为重要&#xff0c;即OTA空中下载…...

mysql迁移步骤

MySQL迁移是指将MySQL数据库从一台服务器迁移到另一台服务器。这可能是因为您需要升级服务器、增加存储空间、提高性能或改变数据库架构。 以下是MySQL迁移的一般步骤&#xff1a; 以上是MySQL迁移的一般步骤&#xff0c;具体步骤可能因您的环境和需求而有所不同。在进行迁移之…...

计算机网络应用层(期末、考研)

计算机网络总复习链接&#x1f517; 目录 DNS域名服务器域名解析过程分类递归查询&#xff08;给根域名服务器造成的负载过大&#xff0c;实际中几乎不用&#xff09;迭代查询 域名缓存&#xff08;了解即可&#xff09;完整域名解析过程采用UDP服务 FTP控制连接与数据连接 电…...

Jenkins离线安装部署教程简记

前言 在上一篇文章基于Gitee实现Jenkins自动化部署SpringBoot项目中&#xff0c;我们了解了如何完成基于Jenkins实现自动化部署。 对于某些公司服务器来说&#xff0c;是不可以连接外网的&#xff0c;所以笔者专门整理了一篇文章总结一下&#xff0c;如何基于内网直接部署Jen…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...

EEG-fNIRS联合成像在跨频率耦合研究中的创新应用

摘要 神经影像技术对医学科学产生了深远的影响&#xff0c;推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下&#xff0c;基于神经血管耦合现象的多模态神经影像方法&#xff0c;通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里&#xff0c;本研…...