摆动序列(力扣376)

2024-04-07 00:12
文章标签 力扣 序列 摆动 376

本文主要是介绍摆动序列(力扣376),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


文章目录

  • 题目
  • 前知
  • 题解
    • 一、思路
    • 二、解题方法
    • 三、Code
  • 总结


在这里插入图片描述

题目

Problem: 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

前知

力扣(LeetCode)第376道题目是“摆动序列”(Wiggle Subsequence),属于动态规划和贪心算法的类型。这道题的要求是找到给定整数序列中最长的摆动子序列的长度。摆动序列是指相邻元素之间的差异在正负之间交替变化。


题解

一、思路

要想得到最大摆动序列的话,只要将单调坡上的结点删除,保留两端的结点,这个坡度就有两个峰值,是局部最优,由局部最优推出全局最优,由于题目只要求返回最大摆动序列的长度,用result变量统计,不用删除结点,用后一个值减去前一个值,得到前prediffcurdiff的值大小,如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 则可以确定存在峰值需要result++
,还有三种特殊情况在下面的解题方法还需要考虑一下

在这里插入图片描述

二、解题方法

本题大概代码是下面这样的:

//只有一个就返回摆动序列长度为1
if (nums.length <= 1) {return nums.length;
}
//计数
int result = 1;for (int i = 1; i < nums.length; i++) {//得到当前差值int curDiff = nums[i] - nums[i - 1];//如果当前差值和上一个差值为一正一负,出现波动就统计if ((prediff < 0 && curdiff > 0) || (prediff > 0 && curdiff < 0)) {result++;}preDiff = curDiff;
}
return count;

三种特殊情况:

  1. 上下坡中有平坡:统一删除靠近左边平坡的点,到最后一个结点时的情况是prediff = 0 && curdiff < 0也要进行记录,所以左边的prediff都要加上与0判断相等的情况
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0))

image.png

  1. 数组首尾两端:当数组只有两个结点时,无法计算出prediffcurdiff,让左边prediff初始为0,这样三个点会根据情况1自动删除左面的一个结点,统计result加1为2,result初始为1,因为nums数组至少都有一个元素,也就是摆动序列长度为1
//当前差值
int curDiff = 0;
//上一个差值
int preDiff = 0;

image.png

  1. 单调坡中有平坡:prediff不能每走一步都进行更新,要等出现波动时,再让prediff等于curdiff。
    在下图中实际上只有数组首尾的1,4是摆动序列里的,result应该为2,但是在平坡的最后一个2的地方因为每走一步prediff都更新下一步的,所以在2的地方也计算了一个波动,只要把prediff更新操作放到if判断里面即可
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {count++;preDiff = curDiff;  // 注意这里,只在摆动变化的时候更新prediff
}

image.png

三、Code

class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length <= 1) {return nums.length;}//当前差值int curDiff = 0;//上一个差值int preDiff = 0;int count = 1;for (int i = 1; i < nums.length; i++) {//得到当前差值curDiff = nums[i] - nums[i - 1];//如果当前差值和上一个差值为一正一负//等于0的情况表示初始时的preDiffif ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {count++;preDiff = curDiff;}}return count;}
}

总结

以上就是针对这道题的刷题笔记,用到了贪心算法从单调坡度上删除中间的结点保留两端的局部最优解推导出整个序列具有最多的局部峰值,达到最长摆动序列,希望这篇题解能够帮助到你解决这个问题。如果有任何疑问或者建议,欢迎留言讨论🌹

这篇关于摆动序列(力扣376)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881200

相关文章

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts?二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与

C# LiteDB处理时间序列数据的高性能解决方案

《C#LiteDB处理时间序列数据的高性能解决方案》LiteDB作为.NET生态下的轻量级嵌入式NoSQL数据库,一直是时间序列处理的优选方案,本文将为大家大家简单介绍一下LiteDB处理时间序列数... 目录为什么选择LiteDB处理时间序列数据第一章:LiteDB时间序列数据模型设计1.1 核心设计原则

Linux中的自定义协议+序列反序列化用法

《Linux中的自定义协议+序列反序列化用法》文章探讨网络程序在应用层的实现,涉及TCP协议的数据传输机制、结构化数据的序列化与反序列化方法,以及通过JSON和自定义协议构建网络计算器的思路,强调分层... 目录一,再次理解协议二,序列化和反序列化三,实现网络计算器3.1 日志文件3.2Socket.hpp

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect