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

leetCode 674. 最长连续递增序列 动态规划 / 贪心策略

674. 最长连续递增序列 - 力扣(LeetCode)

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 rl < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1:

输入:nums = [1,3,5,4,7]
输出:3
解释:最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。 

示例 2:

输入:nums = [2,2,2,2,2]
输出:1
解释:最长连续递增序列是 [2], 长度为1。

 >>思路和分析

本题相对于leetCode 300.最长递增子序列 最大区别在于 “连续”

  • 不连续递增子序列的跟前0-i 个状态有关(两个for循环)
  • 连续递增的子序列只跟前一个状态有关(一个for循环)

>>方法一:动态规划

1.确定dp数组(dp table)以及下标的含义

  • dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]

注意这里的定义,一定是以下标i为结尾,并不是说一定以下标0为起始位置。

2.确定递推公式

如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 

  • 即:dp[i] = dp[i - 1] + 1;

3.dp数组初始化

下标i为结尾的连续递增的子序列长度最少也应该是1,即就是nums[i]这一个元素。所以dp[i]应该初始1;

4.确定遍历顺序

从递推公式上可以看出, dp[i + 1]依赖dp[i],所以一定是从前向后遍历

for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}
}

5.举例推导dp数组

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

>>方法二:贪心策略

当遇到nums[i] > nums[i - 1]的情况,count++,否则count 为 1,记录下count的最大值即可

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int count=1;int result=1;// 连续子序列最少也是1for(int i=1;i<nums.size();i++) {// 连续记录if(nums[i]>nums[i-1]) count = count + 1;// 不连续,count从头开始else count=1;result = max(count,result);}return result;}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

>>来自代码随想录课堂截图:

>>参考和推荐文章、视频

代码随想录 (programmercarl.com)

动态规划之子序列问题,重点在于连续!| LeetCode:674.最长连续递增序列_哔哩哔哩_bilibili

相关文章:

leetCode 674. 最长连续递增序列 动态规划 / 贪心策略

674. 最长连续递增序列 - 力扣&#xff08;LeetCode&#xff09; 给定一个未经排序的整数数组&#xff0c;找到最长且 连续递增的子序列&#xff0c;并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r&#xff08;l < r&#xff09;确定&#xff0c;如果对于每…...

数据中台实战(11)-数据中台的数据安全解决方案

0 微盟删库跑路 除了快、准和省&#xff0c;数据中台须安全&#xff0c;避免“微盟删库跑路”。 2020年2月23日19点&#xff0c;国内最大精准营销服务商微盟出现大面积系统故障&#xff0c;旗下300万商户线上业务全停&#xff0c;商铺后台所有数据被清。始作俑者是一位运维&a…...

林沛满-TCP之在途字节数

本文整理自&#xff1a;《Wireshark网络分析的艺术 第1版》 作者&#xff1a;林沛满 著 出版时间&#xff1a;2016-02 我一直谨记斯蒂芬霍金的金玉良言—每写一道数学公式就会失去一半读者。不过为了深度分析网络包&#xff0c;有时候是不得不计算的&#xff0c;好在小学一年级…...

HTTPS 加密工作过程

引言 HTTP 协议内容都是按照文本的方式明文传输的&#xff0c;这就导致在传输过程中出现一些被篡改的情况。例如臭名昭著的运营商劫持。显然&#xff0c; 明文传输是比较危险的事情&#xff0c;为此引入 HTTPS &#xff0c;HTTPS 就是在 HTTP 的基础上进行了加密, 进一步的来保…...

校招秋招,性格和职业有关系吗?

企业在招聘应届毕业生时不再局限于普通的面试或者笔试&#xff0c;在互联网时代&#xff0c;为了能够更好的匹配需要的优质人才&#xff0c;企业会通过各种测试来提高招聘的准确率以及成功率。也许以前很多人都听说过性格和职业是有一定关系的&#xff0c;但是如何确定自己的性…...

网络和系统操作命令

目录 ping&#xff1a;用于检测网络是否通畅&#xff0c;以及网络时延情况。ipconfig&#xff1a;查看计算机的IP参数配置信息&#xff0c;如IP地址、默认网关、子网掩码等信息。netstat&#xff1a;显示协议统计信息和当前TCP/IP网络连接。tasklist&#xff1a;显示当前运行的…...

刷穿力扣(1~30)

更好的阅读体验 \huge{\color{red}{更好的阅读体验}} 更好的阅读体验 1. 两数之和 哈希表遍历数组&#xff0c;同时用 HashMap 维护已出现过的数及其下标若当前的数 nums[i] 满足 target - nums[i] 曾经出现过&#xff0c;则直接返回否则将其加入到哈希表中。 class Solution …...

栈和队列的基本操作

&#xff08;一&#xff09;实验类型&#xff1a;设计性 &#xff08;二&#xff09;实验目的&#xff1a; 1&#xff0e;掌握栈和队列的抽象数据类型。 2&#xff0e;掌握实现栈和队列的各种操作的算法。 3&#xff0e;理解栈与递归的关系。 4. 掌握队列的链式存贮结构及基…...

变压器绕组断股往往导致直流电阻不平衡率超标

变压器绕组断股往往导致直流电阻不平衡率超标&#xff0c; 例如&#xff0c; 某电厂 SFPSL—12000/220 型主变压器&#xff0c; 色谱分析结果发现总烃含量急剧增长&#xff0c; 测直流电阻&#xff0c; 其结果是高、 低压侧与制造厂及历年的数值相比较无异常&#xff0c; 但中压…...

stack和queque

1.stack 1.1定义 T 是容器内的数据类型&#xff1b; Container是数据类型的容器适配器 vector和list和stack的区别 1.2 stack的功能 注意这里没有迭代器&#xff1b;原因stack是先进后出的规律&#xff1b;这就规定该容器不可以随机访问&#xff1b; 2. queue...

信息学 学习/复习 抽签器(附源码)

问你一个问题&#xff0c;你考试前怎么复习呀&#xff1f; 效果图 以下是源代码&#xff0c;可自行修改 [C] #include<bits/stdc.h> #include<windows.h> using namespace std; vector<string>item; int main(void) {item.push_back("Manacher"…...

基于LADRC自抗扰控制的VSG三相逆变器预同步并网控制策略(Simulink仿真实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

[0xGame 2023] week1

整理一下&#xff0c;昨天该第二周了。今天应该9点结束提交&#xff0c;等我写完就到了。 PWN 找不到且不对劲的flag 第1题是个nc测试&#xff0c;但也不完全是&#xff0c;因为flag在隐含目录里 高端的syscall 程序使用了危险函数&#xff0c;并且没有canary阻止&#xff0…...

Matlab矩阵——矩阵行列互换

问题&#xff1a;如何将 1*n 的矩阵转换为指定 M*N 的矩阵&#xff0c;或者将 M*N 的矩阵转换为 1*n 的矩阵&#xff1f; 处理方法&#xff1a;使用 reshape 函数进行矩阵的行列互换 分两种情况如下&#xff1a; 一、将 1*n 的矩阵转换为指定 M*N 的矩阵 假如有4个坐标值&a…...

OpenMesh 网格面片随机赋色

文章目录 一、简介二、实现代码三、实现效果一、简介 OpenMesh中的赋色方式与Easy3D很是类似,它统一有一个属性数组来进行管理,我们在进行赋色等操作时,必须要首先添加该属性才能进行使用,这里也进行记录一下(法向量等特征也是类似的操作)。 二、实现代码 #define _USE_…...

SpringSecurity源码学习一:过滤器执行原理

目录 1. web过滤器Filter1.1 filter核心类1.2 GenericFilterBean1.3 DelegatingFilterProxy1.3.1 原理1.3.2 DelegatingFilterProxy源码 2. FilterChainProxy源码学习2.1 源码2.1.1 doFilterInternal方法源码2.1.1.1 getFilters()方法源码2.1.1.2 VirtualFilterChain方法源码 3…...

8.2 JUC - 4.Semaphore

目录 一、是什么&#xff1f;二、简单使用三、semaphore应用四、Semaphore原理 一、是什么&#xff1f; Semaphore&#xff1a;信号量&#xff0c;用来限制能同时访问共享资源的线程上限 二、简单使用 public class TestSemaphore {public static void main(String[] args) …...

前端try和catch

为什么要使用try catch 使用try...catch语句是为了处理和管理可能会在程序运行过程中发生的异常或错误情况。以下是一些使用try...catch的主要原因&#xff1a; 错误处理&#xff1a;在开发过程中&#xff0c;无法避免地会出现各种错误&#xff0c;如网络请求失败、数据解析错误…...

Unity可视化Shader工具ASE介绍——2、ASE的Shader创建和输入输出

大家好&#xff0c;我是阿赵&#xff0c;这里继续介绍Unity可视化写Shader的ASE插件的用法。上一篇介绍了ASE的安装和编辑器界面分布&#xff0c;这一篇主要是通过一个简单的例子介绍shader的创建和输入输出。 一、ASE的Shader创建 这里先选择Surface类型的Shader&#xff0c;…...

目标检测算法改进系列之Backbone替换为Swin Transformer

Swin Transformer简介 《Swin Transformer: Hierarchical Vision Transformer using Shifted Windows》作为2021 ICCV最佳论文&#xff0c;屠榜了各大CV任务&#xff0c;性能优于DeiT、ViT和EfficientNet等主干网络&#xff0c;已经替代经典的CNN架构&#xff0c;成为了计算机…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

k8s从入门到放弃之Pod的容器探针检测

k8s从入门到放弃之Pod的容器探针检测 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;容器探测是指kubelet对容器执行定期诊断的过程&#xff0c;以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...

【Java】Ajax 技术详解

文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...