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

数据结构与算法之动态规划: 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 中满足以下要求的最长子序列&#xff1a; 子序列 严格递增子序列中相邻元素的差值 不超过 k请你返回满足上述要求的 最…...

电子电气架构 --- 什么是自动驾驶技术中的域控制单元(DCU)?

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所谓鸡汤,要么蛊惑你认命,要么怂恿你拼命,但都是回避问题的根源,以现象替代逻辑,以情绪代替思考,把消极接受现实的懦弱,伪装成乐观面对不幸的…...

html5css3

1.html5新增语义化标签 <header><nav><article><section><aside><footer> 2.新增多媒体标签 视频<video>格式&#xff1a;map4,webm,ogg <video controls"controls" autoplay"autoplay" muted"mute…...

FPGA多路红外相机视频拼接输出,提供2套工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐我已有的所有工程源码总目录----方便你快速找到自己喜欢的项目我这里已有的红外相机图像处理解决方案本博已有的已有的FPGA视频拼接叠加融合方案 3、工程详细设计方案工程设计原理框图红外相机FDMA多路视频拼接算法FDMA图像缓存视…...

python实战(十二)——如何进行新词发现?

一、概念 新词发现是NLP的一个重要任务&#xff0c;旨在从大量的文本数据中自动识别和提取出未在词典中出现的新词或短语&#xff0c;这对于信息检索、文本挖掘、机器翻译等应用具有重要意义&#xff0c;因为新词往往包含了最新的知识和信息。 随着互联网的不断发展&#xff0c…...

动手做计算机网络仿真实验入门学习

打开软件 work1 添加串行接口模块&#xff0c;先关电源&#xff0c;添加之后再开电源 自动选择连接 所有传输介质 自动连接 串行线 绿色是通的&#xff0c;红色是不通的。 显示接口。se是serial串行的简写。 Fa是fast ethernet的简写。 为计算机配置ip地址&#xff1a; 为服…...

完整的 FFmpeg 命令使用教程

FFmpeg 是一个开源的跨平台音视频处理工具&#xff0c;它能够处理几乎所有的视频、音频格式&#xff0c;并提供了强大的功能如格式转换、视频剪辑、合并、提取音频等。FFmpeg 通过命令行界面&#xff08;CLI&#xff09;操作&#xff0c;尽管有一些图形界面的前端工具&#xff…...

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. 代码实现 题目链接&#xff1a;3405. Count the Number of Arrays with K Matching Adjacent Elements 1. 解题思路 这一题虽然是一道hard的题目&#xff0c;但是委实是有点名不…...

Springboot(五十六)SpringBoot3集成SkyWalking

这里我们将skywalking集成到Springboot中。 关于docker部署skyWalking的相关问题,请移步《docker(二十八)docker-compose部署链路追踪SkyWalking》 一:下载java-agents 先放一下skyWalking的官网下载地址 Downloads | Apache SkyWalking 其他的版本的 APM 地址(这个我不需…...

有没有免费提取音频的软件?音频编辑软件介绍!

出于工作和生活娱乐等原因&#xff0c;有时候我们需要把音频单独提取出来&#xff08;比如歌曲伴奏、人声清唱等、乐器独奏等&#xff09;。要提取音频必须借助音频处理软件&#xff0c;那么有没有免费提取音频的软件呢&#xff1f;下面我们将为大家介绍几款免费软件&#xff0…...

Linux 中查看内存使用情况全攻略

Linux 中查看内存使用情况全攻略 在 Linux 系统运维与开发工作里&#xff0c;精准掌握内存使用状况对系统性能优化、故障排查起着举足轻重的作用。Linux 提供了多款实用工具来查看内存详情&#xff0c;下面我们就结合实际示例&#xff0c;深入了解这些工具的使用方法。 一、fr…...

【SQL Server】教材数据库(3)

接着教材数据库&#xff08;1&#xff09;的内容&#xff0c;完成下列查询。 1 查询订购高等教育出版社教材的学生姓名 2 查询比所有高等教育出版社的图书都贵的图书信息 3 列出每位学生姓名、订购教材书名、价格。 1、嵌套查询&#xff1a;use jiaocai select student.nam…...

使用 ECharts 与 Vue 构建数据可视化组件

在前端开发中&#xff0c;数据可视化是非常重要的一部分。ECharts 作为一个功能强大且易于使用的开源数据可视化库&#xff0c;被广泛应用于各种图表展示需求中。而 Vue.js 是当下流行的前端框架之一&#xff0c;它的数据驱动和组件化开发模式让我们能轻松地将 ECharts 集成到 …...

Yocto 项目 - 共享状态缓存 (Shared State Cache) 机制

引言 在嵌入式开发中&#xff0c;构建效率直接影响项目的开发进度和质量。Yocto 项目通过其核心工具 BitBake 提供了灵活而强大的构建能力。然而&#xff0c;OpenEmbedded 构建系统的传统设计是从头开始构建所有内容&#xff08;Build from Scratch&#xff09;&#xff0c;这…...

Unity3D仿星露谷物语开发9之创建农场Scene

1、目标 绘制农场的场景。通过不同Sorting Layer控制物体的显示优先级&#xff0c;绘制Tilemap地图&#xff0c;添加Tilemap Collider碰撞器&#xff0c;同时添加Composite Collider碰撞器优化性能。 ps&#xff1a;绘制Tilemap的技巧&#xff1a;通过"Shift [" 可…...

STM32-笔记20-测量按键按下时间

1、按键按下的时间-思路 我们先检测下降沿信号&#xff0c;检测到以后&#xff0c;在回调函数里切换成检测上升沿信号&#xff0c;当两个信号都检测到的时候&#xff0c;这段时间就是按键按下的时间&#xff0c;如图所示&#xff1a;>N*(ARR1)CCRx的值 N是在这段时间内&…...

2024年12月30日Github流行趋势

项目名称&#xff1a;free-programming-books 项目地址url&#xff1a;https://github.com/EbookFoundation/free-programming-books项目语言&#xff1a;HTML历史star数&#xff1a;343,398今日star数&#xff1a;246项目维护者&#xff1a;vhf, eshellman, davorpa, MHM5000,…...

SAP PP bom历史导出 ALV 及XLSX 带ECN号

bom总数 104W PS超过XLSX上限 &#xff0c;那就分文件 *&---------------------------------------------------------------------* *& Report ZRPT_PP_BOM_HIS_ECN *&---------------------------------------------------------------------* *& tcode:zpp0…...

使用WebRTC进行视频通信

一、WebRTC技术简介 什么是WebRTC&#xff1f; 是一种支持浏览器之间实时音频、视频和数据传输的开放源代码项目。它允许开发者在不需要任何第三方插件或软件的情况下实现点对点的实时通信。WebRTC已经成为现代Web应用中的关键技术&#xff0c;为开发者提供了强大的工具和API…...

npm ERR! ECONNRESET 解决方法

问题&#xff1a;npm 命令遇到的错误是 ECONNRESET&#xff0c;这通常与网络连接问题相关。设置代理解决问题。 一、查看当前代理设置 npm config get proxy npm config get https-proxy二、设置代理 npm config set proxy http://your-proxy-address:port npm config set h…...

.prettierrc 典型配置(通用版)

文章目录一、完整版标准配置&#xff08;推荐&#xff09;二、极简版配置&#xff08;新手够用&#xff09;三、常用配置项说明&#xff08;一看就懂&#xff09;四、配套使用&#xff08;必看&#xff09;五、总结.prettierrc 典型配置&#xff08;通用版&#xff09;是前端项…...

别再手动导入了!用Pinia + bpmn-js 实现Flowable流程设计的草稿自动恢复与状态管理

基于Pinia与bpmn-js的流程设计器草稿自动恢复方案 在流程设计器的开发过程中&#xff0c;用户最担心的莫过于编辑到一半的流程图因页面刷新或意外关闭而丢失。这种体验问题会直接影响产品的专业性和用户信任度。本文将详细介绍如何利用Vue3生态中的Pinia状态管理库&#xff0c;…...

企业SEO网站推广的优势和劣势有哪些

企业SEO网站推广的优势分析 在当今互联网时代&#xff0c;企业SEO网站推广已经成为一种必不可少的数字营销手段。无论是中小企业还是大型企业&#xff0c;都在竞争激烈的市场中寻找最佳的方式来提升品牌知名度和销售额。企业SEO网站推广究竟有哪些优势呢&#xff1f;以下将从几…...

3.3.1 eUICC Package Download and Execution: A Deep Dive into ES10b and ProfileRollback Mechanisms

1. eUICC包下载与执行的核心流程解析 想象一下你正在给远在另一个城市的智能水表更换运营商服务&#xff0c;就像给手机换SIM卡一样。但这里有个问题&#xff1a;你不可能亲自跑到每个水表旁边插拔SIM卡。这就是eUICC技术大显身手的时候了&#xff0c;它能让物联网设备远程切换…...

openstlinux上利用docker部署ros2humble

STM32MP257F-DK 开发报告&#xff1a;从零部署 OpenSTLinux 与 Docker 容器化 ROS 2 Humble 1. 项目背景与硬件环境 硬件平台&#xff1a;STM32MP257F-DK (双核 Cortex-A35, 4GB RAM, 带 NPU)。存储介质&#xff1a;32GB MicroSD 卡&#xff08;系统自动分区&#xff1a;3.8GB …...

G-Helper终极指南:3分钟解锁华硕笔记本隐藏性能,告别臃肿控制中心!

G-Helper终极指南&#xff1a;3分钟解锁华硕笔记本隐藏性能&#xff0c;告别臃肿控制中心&#xff01; 【免费下载链接】g-helper Lightweight, open-source control tool for ASUS laptops and ROG Ally. Manage performance modes, fans, GPU, battery, and RGB lighting acr…...

SPIRAN ART SUMMONER企业集成:Java面试题中的AI应用解析

SPIRAN ART SUMMONER企业集成&#xff1a;Java面试题中的AI应用解析 掌握AI集成核心考点&#xff0c;轻松应对Java面试中的技术难题 1. 企业级AI集成面试要点 在Java技术面试中&#xff0c;SPIRAN ART SUMMONER这类AI模型的集成能力已经成为衡量候选人综合技术水平的重要标准。…...

程序员必看!高质量免费源码网推荐

在数字化浪潮席卷全球的今天&#xff0c;代码已成为驱动创新的核心动力。无论是初创企业快速搭建商业平台&#xff0c;还是开发者优化项目架构&#xff0c;高质量的源码资源都能显著缩短研发周期、降低开发成本。然而&#xff0c;面对网络上鱼龙混杂的源码平台&#xff0c;如何…...

Python open方法详解

编程中的 open() 方法:核心用法全解 open() 是操作文件的核心方法,几乎所有编程语言(Python、Java、JavaScript 等)都有这个方法,最常用、最适合新手的是 Python 的 open(),我直接给你最实用、能马上用的完整指南。 一、Python open() 基础语法 作用:打开文件,并返回…...

nli-distilroberta-base生产环境:低延迟NLI服务在搜索Query改写中应用

nli-distilroberta-base生产环境&#xff1a;低延迟NLI服务在搜索Query改写中应用 1. 项目概述 在搜索引擎优化和智能问答系统中&#xff0c;Query改写是一个关键环节。nli-distilroberta-base是一个基于DistilRoBERTa模型的轻量级自然语言推理(NLI)服务&#xff0c;专门为生…...