贪心算法----摆动序列

2024-05-12 03:04
文章标签 算法 贪心 序列 摆动

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

今日题目:leetcode376

点击跳转题目

观察样例2:

发现最长摆动序列都是极大值和极小值 再加上两个端点,那么我们保证每次都能选择到每个极值点,就能从局部最优推广全局最优了!

但是还有一些细节情况需要注意,就是如果出现连续相同的值,如图:

  • 对于上图中左边的两种情况,整体是呈现单调递减的,没有出现极值点,不用记录进摆动序列
  • 对于上图中右边的两种情况,是等价于极值点的,只需记录一个进摆动序列即可
  • 综上,遇到连续相同的值时,我们只需要考虑相同值中最靠后的位置的那个值,其他的忽略,这样就转化为把相同元素”删除“成只剩一个元素的情况

遍历数组时,我们可以用一个left来记录这个值左边是递增还是递减,然后和这个数的右边判断,单调性不同即可记录该元素

代码:

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int cnt = 0;//记录每个元素左边的单调性,初始为0为了记录第一个值为摆动元素int left = 0;for(int i = 0; i < nums.size() - 1; i++){int right = nums[i+1] - nums[i]; //得出右边的单调性if(right == 0) continue;//符号相反,表示单调性不同,是极值点if(left * right <= 0) cnt++;       left = right;//迭代为下一个元素左边的单调性}return cnt+1; //+1是为了记录原数组最后一个值}
};

这篇关于贪心算法----摆动序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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时我们针对

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

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

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

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

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

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

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n