数据结构与算法之动态规划: LeetCode 2407. 最长递增子序列 II (Ts版)
最长递增子序列 II
- https://leetcode.cn/problems/longest-increasing-subsequence-ii/description/
描述
- 给你一个整数数组 nums 和一个整数 k
- 找到 nums 中满足以下要求的最长子序列:
- 子序列 严格递增
- 子序列中相邻元素的差值 不超过 k
- 请你返回满足上述要求的 最长子序列 的长度
- 子序列 是从一个数组中删除部分元素后,剩余元素不改变顺序得到的数组
示例 1
输入:nums = [4,2,1,4,3,4,5,8,15], k = 3
输出:5
解释:
满足要求的最长子序列是 [1,3,4,5,8]
子序列长度为 5 ,所以我们返回 5
注意子序列 [1,3,4,5,8,15] 不满足要求,因为 15 - 8 = 7 大于 3
示例 2
输入:nums = [7,4,5,1,8,12,4,7], k = 5
输出:4
解释:
满足要求的最长子序列是 [4,5,8,12]
子序列长度为 4 ,所以我们返回 4
示例 3
输入:nums = [1,5], k = 1
输出:1
解释:
满足要求的最长子序列是 [1]
子序列长度为 1 ,所以我们返回 1
提示
- 1 <= nums.length <= 1 0 5 10^5 105
- 1 <= nums[i], k <= 1 0 5 10^5 105
Typescript 版算法实现
1 ) 方案1: 线段树
function lengthOfLIS(nums: number[], k: number): number {if (nums.length === 0) return 0;const u = Math.max(...nums); // 找到 nums 中的最大值const max = new Array(u * 4).fill(0); // 初始化段树数组function modify(o: number, l: number, r: number, i: number, val: number): void {if (l === r) {max[o] = val;return;}const m = Math.floor((l + r) / 2);if (i <= m) modify(o * 2, l, m, i, val);else modify(o * 2 + 1, m + 1, r, i, val);max[o] = Math.max(max[o * 2], max[o * 2 + 1]);}function query(o: number, l: number, r: number, L: number, R: number): number {if (L <= l && r <= R) return max[o];let res = 0;const m = Math.floor((l + r) / 2);if (L <= m) res = query(o * 2, l, m, L, R);if (R > m) res = Math.max(res, query(o * 2 + 1, m + 1, r, L, R));return res;}for (const x of nums) {if (x === 1) modify(1, 1, u, 1, 1);else {const res = 1 + query(1, 1, u, Math.max(x - k, 1), x - 1);modify(1, 1, u, x, res);}}return max[1]; // 段树根节点存储了整个区间的最大值
}
相关文章:
数据结构与算法之动态规划: LeetCode 2407. 最长递增子序列 II (Ts版)
最长递增子序列 II https://leetcode.cn/problems/longest-increasing-subsequence-ii/description/ 描述 给你一个整数数组 nums 和一个整数 k找到 nums 中满足以下要求的最长子序列: 子序列 严格递增子序列中相邻元素的差值 不超过 k请你返回满足上述要求的 最…...
电子电气架构 --- 什么是自动驾驶技术中的域控制单元(DCU)?
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所谓鸡汤,要么蛊惑你认命,要么怂恿你拼命,但都是回避问题的根源,以现象替代逻辑,以情绪代替思考,把消极接受现实的懦弱,伪装成乐观面对不幸的…...
html5css3
1.html5新增语义化标签 <header><nav><article><section><aside><footer> 2.新增多媒体标签 视频<video>格式:map4,webm,ogg <video controls"controls" autoplay"autoplay" muted"mute…...
FPGA多路红外相机视频拼接输出,提供2套工程源码和技术支持
目录 1、前言工程概述免责声明 2、相关方案推荐我已有的所有工程源码总目录----方便你快速找到自己喜欢的项目我这里已有的红外相机图像处理解决方案本博已有的已有的FPGA视频拼接叠加融合方案 3、工程详细设计方案工程设计原理框图红外相机FDMA多路视频拼接算法FDMA图像缓存视…...
python实战(十二)——如何进行新词发现?
一、概念 新词发现是NLP的一个重要任务,旨在从大量的文本数据中自动识别和提取出未在词典中出现的新词或短语,这对于信息检索、文本挖掘、机器翻译等应用具有重要意义,因为新词往往包含了最新的知识和信息。 随着互联网的不断发展,…...
动手做计算机网络仿真实验入门学习
打开软件 work1 添加串行接口模块,先关电源,添加之后再开电源 自动选择连接 所有传输介质 自动连接 串行线 绿色是通的,红色是不通的。 显示接口。se是serial串行的简写。 Fa是fast ethernet的简写。 为计算机配置ip地址: 为服…...
完整的 FFmpeg 命令使用教程
FFmpeg 是一个开源的跨平台音视频处理工具,它能够处理几乎所有的视频、音频格式,并提供了强大的功能如格式转换、视频剪辑、合并、提取音频等。FFmpeg 通过命令行界面(CLI)操作,尽管有一些图形界面的前端工具ÿ…...
Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements
Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements 1. 解题思路2. 代码实现 题目链接:3405. Count the Number of Arrays with K Matching Adjacent Elements 1. 解题思路 这一题虽然是一道hard的题目,但是委实是有点名不…...
Springboot(五十六)SpringBoot3集成SkyWalking
这里我们将skywalking集成到Springboot中。 关于docker部署skyWalking的相关问题,请移步《docker(二十八)docker-compose部署链路追踪SkyWalking》 一:下载java-agents 先放一下skyWalking的官网下载地址 Downloads | Apache SkyWalking 其他的版本的 APM 地址(这个我不需…...
有没有免费提取音频的软件?音频编辑软件介绍!
出于工作和生活娱乐等原因,有时候我们需要把音频单独提取出来(比如歌曲伴奏、人声清唱等、乐器独奏等)。要提取音频必须借助音频处理软件,那么有没有免费提取音频的软件呢?下面我们将为大家介绍几款免费软件࿰…...
Linux 中查看内存使用情况全攻略
Linux 中查看内存使用情况全攻略 在 Linux 系统运维与开发工作里,精准掌握内存使用状况对系统性能优化、故障排查起着举足轻重的作用。Linux 提供了多款实用工具来查看内存详情,下面我们就结合实际示例,深入了解这些工具的使用方法。 一、fr…...
【SQL Server】教材数据库(3)
接着教材数据库(1)的内容,完成下列查询。 1 查询订购高等教育出版社教材的学生姓名 2 查询比所有高等教育出版社的图书都贵的图书信息 3 列出每位学生姓名、订购教材书名、价格。 1、嵌套查询:use jiaocai select student.nam…...
使用 ECharts 与 Vue 构建数据可视化组件
在前端开发中,数据可视化是非常重要的一部分。ECharts 作为一个功能强大且易于使用的开源数据可视化库,被广泛应用于各种图表展示需求中。而 Vue.js 是当下流行的前端框架之一,它的数据驱动和组件化开发模式让我们能轻松地将 ECharts 集成到 …...
Yocto 项目 - 共享状态缓存 (Shared State Cache) 机制
引言 在嵌入式开发中,构建效率直接影响项目的开发进度和质量。Yocto 项目通过其核心工具 BitBake 提供了灵活而强大的构建能力。然而,OpenEmbedded 构建系统的传统设计是从头开始构建所有内容(Build from Scratch),这…...
Unity3D仿星露谷物语开发9之创建农场Scene
1、目标 绘制农场的场景。通过不同Sorting Layer控制物体的显示优先级,绘制Tilemap地图,添加Tilemap Collider碰撞器,同时添加Composite Collider碰撞器优化性能。 ps:绘制Tilemap的技巧:通过"Shift [" 可…...
STM32-笔记20-测量按键按下时间
1、按键按下的时间-思路 我们先检测下降沿信号,检测到以后,在回调函数里切换成检测上升沿信号,当两个信号都检测到的时候,这段时间就是按键按下的时间,如图所示:>N*(ARR1)CCRx的值 N是在这段时间内&…...
2024年12月30日Github流行趋势
项目名称:free-programming-books 项目地址url:https://github.com/EbookFoundation/free-programming-books项目语言:HTML历史star数:343,398今日star数:246项目维护者:vhf, eshellman, davorpa, MHM5000,…...
SAP PP bom历史导出 ALV 及XLSX 带ECN号
bom总数 104W PS超过XLSX上限 ,那就分文件 *&---------------------------------------------------------------------* *& Report ZRPT_PP_BOM_HIS_ECN *&---------------------------------------------------------------------* *& tcode:zpp0…...
使用WebRTC进行视频通信
一、WebRTC技术简介 什么是WebRTC? 是一种支持浏览器之间实时音频、视频和数据传输的开放源代码项目。它允许开发者在不需要任何第三方插件或软件的情况下实现点对点的实时通信。WebRTC已经成为现代Web应用中的关键技术,为开发者提供了强大的工具和API…...
npm ERR! ECONNRESET 解决方法
问题:npm 命令遇到的错误是 ECONNRESET,这通常与网络连接问题相关。设置代理解决问题。 一、查看当前代理设置 npm config get proxy npm config get https-proxy二、设置代理 npm config set proxy http://your-proxy-address:port npm config set h…...
利用快马平台与ccswitch快速构建可切换功能模块的web应用原型
今天想和大家分享一个快速验证前端功能模块切换方案的小技巧。最近在做一个需要动态切换不同功能模块的项目,尝试了用ccswitch工具配合InsCode(快马)平台来搭建原型,效果出乎意料地好。 为什么选择ccswitch ccswitch是一个轻量级的JavaScript工具&…...
解锁Noria查询重用机制:如何智能复用数据流组件实现应用性能飞跃
解锁Noria查询重用机制:如何智能复用数据流组件实现应用性能飞跃 【免费下载链接】noria Fast web applications through dynamic, partially-stateful dataflow 项目地址: https://gitcode.com/gh_mirrors/no/noria 在现代Web应用开发中,性能优化…...
Qwen-Image-Edit-F2P结合YOLOv8实现智能人像编辑:目标检测应用案例
Qwen-Image-Edit-F2P结合YOLOv8实现智能人像编辑:目标检测应用案例 你有没有想过,给照片里的人换个发型、加副眼镜,或者换个背景,能有多简单?过去这可能需要专业的设计师,花上不少时间在Photoshop里一点点…...
OpenClaw多端同步:千问3.5-9B任务在手机与PC间无缝衔接
OpenClaw多端同步:千问3.5-9B任务在手机与PC间无缝衔接 1. 为什么需要跨设备任务同步? 去年冬天的一个深夜,我正躺在沙发上用手机浏览技术文档,突然想到需要运行一个数据分析脚本。但电脑在书房,实在不想起身。那一刻…...
uosc与其他MPV脚本对比:为什么uosc是极简MPV播放器UI的终极选择
uosc与其他MPV脚本对比:为什么uosc是极简MPV播放器UI的终极选择 【免费下载链接】uosc Feature-rich minimalist proximity-based UI for MPV player. 项目地址: https://gitcode.com/gh_mirrors/uo/uosc 在众多MPV播放器UI脚本中,uosc以其独特的…...
OpenClaw浏览器自动化:千问3.5-35B-A3B-FP8驱动智能爬虫实践
OpenClaw浏览器自动化:千问3.5-35B-A3B-FP8驱动智能爬虫实践 1. 为什么需要AI驱动的浏览器自动化 去年我接手了一个数据采集项目,目标是从几十个电商平台抓取商品信息和用户评价。传统爬虫在遇到验证码、动态加载内容时频繁失效,而人工操作…...
Whisper JAX自定义模型训练终极指南:从PyTorch到Flax的完整转换流程
Whisper JAX自定义模型训练终极指南:从PyTorch到Flax的完整转换流程 【免费下载链接】whisper-jax JAX implementation of OpenAIs Whisper model for up to 70x speed-up on TPU. 项目地址: https://gitcode.com/gh_mirrors/wh/whisper-jax Whisper JAX是基…...
OpenClaw浏览器自动化:Phi-3-mini-128k-instruct操控Chrome完成数据采集
OpenClaw浏览器自动化:Phi-3-mini-128k-instruct操控Chrome完成数据采集 1. 为什么选择OpenClaw做浏览器自动化? 去年我在做一个市场调研项目时,需要从几十个网页中提取产品参数和价格信息。传统爬虫遇到动态加载的页面就束手无策ÿ…...
零代码建站!免费源码网快速上手
在数字化浪潮席卷各行各业的今天,拥有一个专业网站已成为个人展示、企业宣传、产品推广的标配。然而,传统网站开发需要专业的技术团队、高昂的开发成本和漫长的建设周期,这让许多初创企业、个人站长望而却步。幸运的是,随着"…...
Agent 记忆全景综述:20+顶尖机构联合出品,Agent memory看这一篇就够了
用 GPT 或 Claude 做过长对话的人大概都踩过这个坑:聊了半个小时,AI 把你前面说过的事情忘干净了。你不得不把背景重新解释一遍。 这还是人机对话,忍一忍也就算了。 但如果是 agent 在自主执行任务呢?记不住"这个 API 上次…...
