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. 从链表中移除节点【栈 递归 链表 单调栈】 题目描述:解题思路一:可以将链表转为数组,然后从后往前遍历,遇到大于等于当前元素的就入栈,最终栈里面的元素即是最终的答案。解题思路二:递归&am…...
Redisson分布式锁原理分析
1.Redisson实现分布式锁 在分布式系统中,涉及到多个实例对同一资源加锁的情况,传统的synchronized、ReentrantLock等单进程加锁的API就不再适用,此时就需要使用分布式锁来保证多服务之间加锁的安全性。 常见的分布式锁的实现方式有ÿ…...
【Linux】:线程(二)互斥
互斥与同步 一.线程的局部存储二.线程的分离三.互斥1.一些概念2.上锁3.锁的原理4.死锁 一.线程的局部存储 例子 可以看到全局变量是所有线程共享的,如果我们想要每个线程都单独访问g_val怎么办呢?其实我们可以在它前面加上__thread修饰。 这就相当于把g…...
vscode报错Pylance client: couldn‘t create connection to server.
问题描述: 一打开vscode,右下角就弹报错,Pylance client: couldn’t create connection to server.,让我打开output,打开后似乎是在说连不上server 因为连不上server,所以我的python代码没法解析࿰…...
智能优化算法应用:基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.萤火虫算法4.实验参数设定5.算法结果6.参考文…...
MacOS多屏状态栏位置不固定,程序坞不小心跑到副屏
目录 方式一:通过系统设置方式二:鼠标切换 MacOS多屏状态栏位置不固定,程序坞不小心跑到副屏 方式一:通过系统设置 先切换到左边 再切换到底部 就能回到主屏了 方式二:鼠标切换 我的两个屏幕放置位置如下 鼠标在…...
Python:pipdeptree 语法介绍
相信大家在按照一些包的时候经常会碰到版本不兼容,但是又不知道版本之间的依赖关系,今天给大家介绍一个工具:pipdeptree pipdeptree 是一个 Python 包,用于查看已安装的 pip 包及其依赖关系。它以树形结构展示包之间的依赖关系&am…...
【问题处理】—— lombok 的 @Data 大小写区分不敏感
问题描述 今天在项目本地编译的时候,发现有个很奇怪的问题,一直提示某位置找不到符号, 但是实际在Idea中显示确实正常的,一开始以为又是IDEA的故障,所以重启了IDEA,并执行了mvn clean然后重新编译。但是问…...
跟着我学Python基础篇:08.集合和字典
往期文章 跟着我学Python基础篇:01.初露端倪 跟着我学Python基础篇:02.数字与字符串编程 跟着我学Python基础篇:03.选择结构 跟着我学Python基础篇:04.循环 跟着我学Python基础篇:05.函数 跟着我学Python基础篇&#…...
Tomcat部署(图片和HTML等)静态资源时遇到的问题
文章目录 Tomcat部署静态资源问题图中HTML代码启动Tomcat后先确认Tomcat是否启动成功 Tomcat部署静态资源问题 今天,有人突然跟我提到,使用nginx部署静态资源,如图片。可以直接通过url地址访问,为什么他的Tomcat不能通过这样的方…...
在接触新的游戏引擎的时候,如何能快速地熟悉并开发出一款新游戏?
引言 大家好,今天分享点个人经验。 有一定编程经验或者游戏开发经验的小伙伴,在接触新的游戏引擎的时候,如何能快速地熟悉并开发出一款新游戏? 利用现成开发框架。 1.什么是开发框架? 开发框架,顾名思…...
计网 - TCP四次挥手原理全曝光:深度解析与实战演示
文章目录 Pre导图过程分析抓包实战第一次挥手 【FIN ACK】第二次挥手 【ACK】第三次挥手 【FINACK】第四次挥手 【ACK】 小结 Pre 计网 - 传输层协议 TCP:TCP 为什么握手是 3 次、挥手是 4 次? 计网 - TCP三次握手原理全曝光:深度解析与实战…...
个人养老金知多少?
个人养老金政策你了解吗?税优政策你知道吗?你会计算能退多少税吗?… 点这里看一看...
gpt3、gpt2与gpt1区别
参考:深度学习:GPT1、GPT2、GPT-3_HanZee的博客-CSDN博客 Zero-shot Learning / One-shot Learning-CSDN博客 Zero-shot(零次学习)简介-CSDN博客 GPT1、GPT2、GPT3、InstructGPT-CSDN博客 目录 gpt2与gpt1区别: gp…...
PyQt6 QDateEdit日期控件
锋哥原创的PyQt6视频教程: 2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计39条视频,包括:2024版 PyQt6 Python桌面开发 视频教程(无废话…...
【无线网络技术】——无线城域网(学习笔记)
📖 前言:无线城域网(WMAN)是指在地域上覆盖城市及其郊区范围的分布节点之间传输信息的本地分配无线网络。能实现语音、数据、图像、多媒体、IP等多业务的接入服务。其覆盖范围的典型值为3~5km,点到点链路的覆盖可以高达…...
RK3568平台 OTA升级原理
一.前言 在迅速变化和发展的物联网市场,新的产品需求不断涌现,因此对于智能硬件设备的更新需求就变得空前高涨,设备不再像传统设备一样一经出售就不再变更。为了快速响应市场需求,一个技术变得极为重要,即OTA空中下载…...
mysql迁移步骤
MySQL迁移是指将MySQL数据库从一台服务器迁移到另一台服务器。这可能是因为您需要升级服务器、增加存储空间、提高性能或改变数据库架构。 以下是MySQL迁移的一般步骤: 以上是MySQL迁移的一般步骤,具体步骤可能因您的环境和需求而有所不同。在进行迁移之…...
计算机网络应用层(期末、考研)
计算机网络总复习链接🔗 目录 DNS域名服务器域名解析过程分类递归查询(给根域名服务器造成的负载过大,实际中几乎不用)迭代查询 域名缓存(了解即可)完整域名解析过程采用UDP服务 FTP控制连接与数据连接 电…...
Jenkins离线安装部署教程简记
前言 在上一篇文章基于Gitee实现Jenkins自动化部署SpringBoot项目中,我们了解了如何完成基于Jenkins实现自动化部署。 对于某些公司服务器来说,是不可以连接外网的,所以笔者专门整理了一篇文章总结一下,如何基于内网直接部署Jen…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
