当前位置: 首页 > 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…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

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…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...