当前位置: 首页 > 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;成为了计算机…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...