(贪心) LeetCode 376. 摆动序列

原题链接

一. 题目描述

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1:

输入:nums = [1,7,4,9,2,5]
输出:6
解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2:

输入:nums = [1,17,5,10,13,15,10,5,16,8]
输出:7
解释:这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3:

输入:nums = [1,2,3,4,5,6,7,8,9]
输出:2
 

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
 

进阶:你能否用 O(n) 时间复杂度完成此题?

二. 解题思路

这个题目的意思就是让我们寻找最长的摆动序列,连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列。如果之间有数字不构成摆动序列,那么就可以删除一些元素从而让序列摆动。

题意很简单,但是做起来不知道怎么写?你难道真的准备判断是否摆动,然后遇到不是摆动序列的元素删除它吗?不不不,跳过不就好了,题目没有明确要求必须删除元素,我们只需要跳过该元素判断后面的元素是否摆动即可,最后只需要输出摆动序列的最长长度即可。

在计算是否有峰值的时候,大家知道遍历的下标 i ,计算 prediff(nums[i] - nums[i-1]) 和 curdiff(nums[i+1] - nums[i]),如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。

下面可以将情况分为三种:

1. 上下坡中存在平坡:

 像这种类型的我们只需要从左到右或者从右到左删除三个2就可以构成摆动序列了(如下图所示):

如果我们采用,删左面三个 2 的规则,那么 当 predif = 0 && curdif < 0 也要记录一个峰值,因为他是把之前相同的元素都删掉留下的峰值。

所以我们记录峰值的条件应该是: (predif <= 0 && curdif > 0) || (predif >= 0 && curdif < 0),为什么这里允许 prediff == 0 ,就是为了 上面的这种情况。

2. 数组的首尾两端:

大家可以发现,我们在上面计算predif 和curdif 的时候至少需要三个元素才能完成计算,那要是序列中只有两个元素呢?如[1, 2],题目中明确要求,如果两个元素,存在两个摆动。那我们怎么将这种情况算到上面的哦按段条件中呢?

很简单,只需要给序列的首元素添加一个平坡即可(如下图所示),将序列[2, 5] 变为 [2, 2, 5]:

 这样也就对 predif 就可以计算为 0 ,那末尾怎么算呢?其实我们末尾默认是有一个峰值的,所以我们将结果集 res 默认为 1 即可。这样就可以得到最后的 res 为2。

这样我们就可以得到一个代码:

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();int curDiff = 0; // 当前一对差值int preDiff = 0; // 前一对差值int result = 1;  // 记录峰值个数,序列默认序列最右边有一个峰值for (int i = 0; i < nums.size() - 1; i++) {curDiff = nums[i + 1] - nums[i];// 出现峰值if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {result++;}preDiff = curDiff;}return result;}
};

3. 单调坡度有平坡:

什么叫单调坡度有平坡呢,看下图就可以明白了:

从上图中大家觉得答案是多少, 应该是2,但是我们如果按照上面的代码计算方法会算出来3 ,显然是不对的,为什么呢,原因就是我们每一次都会将curdif 赋值给 predif ,但是遇到这种情况的平坡的时候,在最后一个2 处 predif = 0,然后后面计算的 curdif = 1。满足上面的判断条件,就会多加一次,实际上这里不存在摆动,这也就是我们代码中的一个逻辑性的错误。

对于解决上面的错误方法很简单,只需要将 predif = curdif 这个赋值代码加入到判断条件内部即可,保证摆动的前提是相较于上一次的摆动,而不是最近区间的摆动,这样prediff 在 单调区间有平坡的时候 就不会发生变化,从而避免误判。

话不多说!!!上代码!!

三. 代码

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int res = 1;int predif = 0;int curdif = 0;int n = nums.size();for(int i = 0; i < n - 1; i++){curdif = nums[i + 1] - nums[i];if((predif >= 0 && curdif < 0) || (predif <= 0 && curdif > 0)){res++;predif = curdif;}}return res;}
};

四. 总结

这个题目还是比较绕的,需要考虑很多种情况,我感觉是比较难的一道题目,刚开始做的时候确实有点难懂,但是大家一定要多去看,多去理解,在本子上列举情况去分析,这样才能有进步,加油!!!。

时间复杂度:O(n);

空间复杂度:O(1)。

喜欢的话给个关注吧!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/401160.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【LeetCode每日一题】——623.在二叉树中增加一行

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 广度优先遍历 二【题目难度】 中等 三【题目编号】 623.在二叉树中增加一行 四【题目描述】…

【每日刷题】Day100

【每日刷题】Day100 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 【模板】堆_牛客题霸_牛客网 (nowcoder.com) 2. 【模板】链表_牛客题霸_牛客网 (nowcoder.com) 3…

红酒与旅游攻略:旅行途中的风味之选

在旅行的道路上&#xff0c;我们总是渴望寻找那些能够触动心灵、留下深刻记忆的不同体验。而红酒&#xff0c;作为一种充满韵味和故事的饮品&#xff0c;无疑是旅行途中的风味之选。洒派红酒&#xff08;Bold & Generous&#xff09;&#xff0c;这款定制红酒&#xff0c;以…

【公式推导】Elucidating the Design Space of Diffusion-Based Generative Models 【论文精读】

Elucidating the Design Space of Diffusion-Based Generative Models 论文精读 关注B站可以观看更多实战教学视频&#xff1a;hallo128的个人空间 【更新中】EDM论文精读 论文链接 &#xff08;1&#xff09;论文&#xff1a;Elucidating the Design Space of Diffusion-Base…

连接投影仪/显示器只能扩展不能复制的解决方案

原文章&#xff1a;https://iknow.lenovo.com.cn/detail/121481 故障现象&#xff1a; 笔记本外接投影仪/显示器后&#xff0c;笔记本屏幕有显示&#xff0c;但投影仪却只有背景或没有显示&#xff1b; 原因分析&#xff1a; 此现象多发生在双显卡机型上&#xff0c;笔记本屏…

旺店通·企业奇门对接打通旺店通·企业奇门库存查询接口与创建盘点单接口

旺店通企业奇门对接打通旺店通企业奇门库存查询接口与创建盘点单接口 接入系统&#xff1a;旺店通企业奇门 慧策&#xff08;原旺店通&#xff09;是一家技术驱动型智能零售服务商&#xff0c;基于云计算PaaS、SaaS模式&#xff0c;以一体化智能零售解决方案&#xff0c;帮助零…

Python爬虫与数据分析:中国大学排名的深度挖掘

前言 &#x1f449; 小编已经为大家准备好了完整的代码和完整的Python学习资料&#xff0c;朋友们如果需要可以扫描下方CSDN官方认证二维码或者点击链接免费领取【保证100%免费】 一、选题背景 高考作为中国学生生涯中最为重要的事&#xff0c;在高考之后&#xff0c;选择一所…

Vision Transformer学习笔记

论文链接&#xff1a;https://arxiv.org/abs/2010.11929 项目链接&#xff1a;https://github.com/google-research/vision_transformer 本文代码链接&#xff1a;https://gitcode.com/gh_mirrors/de/deep-learning-for-image-processing/tree/master/pytorch_classification/v…

大模型面试系列-大模型算法工程师的面试题目与解答技巧详细说明

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下大模型面试系列-大模型算法工程师的面试题目与解答技巧详细说明。 文章目录 大模型算法工程师面试题1. Llama 2 中使用的注意力机制是什么&#xff1f;描述一下查询分组注意力。2. LangChain 的结构详细描述一下。…

【go语言】go-webview2用法(持续更新)

文章目录 背景核心接口和方法扩展接口遗憾的是 背景 目前为止&#xff0c;已经有很多优秀的electron应用。但其特点也很明显&#xff1a;使用htmlcssjs构建的布局很精致&#xff0c;但是体积不容小觑&#xff08;最新版electron-egg打包出来的程序已经300MB&#xff09;。 vs…

014集——浮点数值类型——C#学习笔记

浮点类型的特征 C# 支持以下预定义浮点类型&#xff1a; double a 12.3; System.Double b 12.3; 每个浮点类型的默认值都为零&#xff0c;0。 每个浮点类型都有 MinValue 和 MaxValue 常量&#xff0c;提供该类型的最小值和最大有限值。 float and double 类型还提供可表示非…

开放大世界的 GpuTerrain + RVT

Unity 原生有一个 Tarrain&#xff08;地形&#xff09;系统&#xff0c;但可惜并不能直接用于开放世界&#xff0c;当然是因为其效率问题。现在开放世界主流是使用 GpuTerrain RVT &#xff0c;也是一个成熟技术了。在项目中实现这个技术的是公司的 TA&#xff08;我只做了接…

学习计算机网络(三)——IP地址

一、IP协议&#xff08;IPV4、IPV6&#xff09; 表示形式&#xff08;两种&#xff09;&#xff1a; 点分十进制、二进制 地址被点分为4个部分&#xff0c;每个部分8位&#xff0c;总共32位。 A、B、C类地址都是单播地址&#xff08;一对一通信&#xff09;&#xff0c;D类…

kubernetes k8s Daemonset 控制器 原理 讲解 配置

目录 1 DaemonSet控制器&#xff1a;概念、原理解读 1.1 DaemonSet概述 1.2 DaemonSet工作原理&#xff1a;如何管理Pod&#xff1f; 1.3 Daemonset典型的应用场景 1.4 DaemonSet 与 Deployment 的区别Deployment 部署的副本 Pod 会分布在各个 Node 上&#xff0c;每个…

Python轻量级 NoSQL 数据库之tinydb使用详解

概要 在现代应用开发中,使用数据库来存储和管理数据是非常常见的需求。对于简单的数据存储需求,关系型数据库可能显得过于复杂。TinyDB 是一个纯 Python 实现的轻量级 NoSQL 数据库,专为嵌入式场景设计,适用于小型项目、原型开发和教学等场景。本文将详细介绍 TinyDB 库,…

宠物行为:健康信号的早期预警

宠物&#xff0c;作为我们家庭中不可或缺的一部分&#xff0c;它们的健康同样需要我们细心呵护。宠物的行为变化&#xff0c;往往预示着健康问题的出现。而智能科技的融入&#xff0c;让这一过程变得更加科学和精准。 智能听诊器&#xff1a;宠物健康的守护者 智能听诊器&…

ISO 13485认证:医疗器械行业的质量护航者

在医疗器械行业&#xff0c;产品质量关乎生命。为确保每一件医疗器械的安全与可靠&#xff0c;ISO 13485认证作为全球公认的质量管理体系标准&#xff0c;正为无数企业提供强大的质量保障。对于企业来说&#xff0c;获得这一认证不仅是质量管理的提升&#xff0c;更是开拓全球市…

时间序列分析详解

时间序列分析详解 时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列。 分析时间序 列的方法构成数据分析的一个重要领域&#xff0c;即时间序列分析。 时间序列根据所研究的依据不同&#xff0c;可有不同的分类。 按所研究的对象的多少分&#xff0c;有一元时间序…

Spring Cloud Alibaba微服务组件学习笔记

文章目录 一、版本说明版本关系项目创建 二、Nacos注册中心什么是NacosNacos注册中心核心功能Nacos Server部署&#xff08;windows版本&#xff09;Nacos Client服务Nacos Server配置项详解&#xff1a;Nacos集群搭建&#xff1a; 三、Ribbon负载均衡主流的负载方案&#xff1…

Spark MLlib 特征工程(上)

文章目录 Spark MLlib 特征工程(上)特征工程预处理 Encoding:StringIndexer特征构建:VectorAssembler特征选择:ChiSqSelector归一化:MinMaxScaler模型训练总结Spark MLlib 特征工程(上) 前面我们一起构建了一个简单的线性回归模型,来预测美国爱荷华州的房价。从模型效果来…