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

03贪心:摆动序列

03贪心:摆动序列

376. 摆动序列

局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值

整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列

局部最优推出全局最优,并举不出反例,那么试试贪心!

实际操作上,其实连删除的操作都不用做,因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点,然后统计长度)

这就是贪心所贪的地方,让峰值尽可能的保持峰值,然后删除单一坡度上的节点

这是我们思考本题的一个大题思路,但本题要考虑三种情况:

  1. 情况一:上下坡中有平坡
  2. 情况二:数组首尾两端
  3. 情况三:单调坡中有平坡
class Solution {//贪心:要想成为摆动序列,只需要吧每一条单调坡除峰值以外的其他元素删除即可(局部最优),那么整个数组就是摆动序列(整体最优)public int wiggleMaxLength(int[] nums) {//一般情况:prediff记录左边的方向,curdiff记录右边的方向,如果两值一正一负则result++int prediff = 0;int curdiff = 0;int result = 1;//@2/*几点特殊情况1.上下坡中有平坡1 2 2 1 prediff = 0,curdiff != 0 @12.考虑首尾元素1 2 这是两个长度,假设数组是1 1 2,起始位置左边假设是个平坡,那么就满足第一种特殊情况可以加一,另外,总是假设数组的最右侧是一个长度,因为它必是一个峰值@23.单调坡中有平坡1 2 2 3 (我们判断的是最后一个数字也就是第二个2)对于第二个2来说,prediff=0,curdiff!=0,应该算一个,但是并不是,因为这不是上下坡我们怎么知道不是呢,得通过prediff来判断,如果这个prediff记录的是1 2之间的坡度我就能判断出来这不是答案,也就是说prediff的更新下手解决解决办法:当坡度有变化的时候再进行更新,就是说result有变化的时候,坡度就肯定有变化回到第一种特殊情况,1 2 2 1prediff记录1 2 的坡度,curdiff记录的是2 1的坡度,符合*/for(int i = 0; i < nums.length - 1; i++) {//因为假设最后一个数已经计算上了,res=1curdiff = nums[i + 1] - nums[i];//prediff * curdiff <= 0不行,这只能保证两个坡度至少有一个为0,如果是0 0的话就错了if((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) {//@1   如果curdiff等于0就不用管了,向右遍历就可以了result++;prediff = curdiff;//@3}//prediff = curdiff;不用且不能实时更新}return result;}
}

相关文章:

03贪心:摆动序列

03贪心&#xff1a;摆动序列 376. 摆动序列 局部最优&#xff1a;删除单调坡度上的节点&#xff08;不包括单调坡度两端的节点&#xff09;&#xff0c;那么这个坡度就可以有两个局部峰值。 整体最优&#xff1a;整个序列有最多的局部峰值&#xff0c;从而达到最长摆动序列。…...

javascript获取元素在浏览器中工作区域的左、右、上、下距离,或带滚动条的元素在页面中的大小

//获取元素在包含元素框中的大小 //第1个函数为获取元素在包含元素中左内边框的距离 function getELementLeft(element){//获取元素在包含元素左边距离var actualeftelement.offsetLeft;//获取元素的上级包含元素var currentelement.offsetParent;//循环到一直没有包含元素whil…...

VSCode 安装使用教程 环境安装配置 保姆级教程

一个好用的 IDE 不仅能提升我们的开发效率&#xff0c;还能让我们保持愉悦的心情&#xff0c;这样才是非常 Nice 的状态 ^_^ 那么&#xff0c;什么是 IDE 呢 &#xff1f; what IDE&#xff08;Integrated Development Environment&#xff0c;集成开发环境&#xff09;是含代码…...

c盘中temp可以删除吗?appdata\local\temp可以删除吗?

http://www.win10d.com/jiaocheng/22594.html C盘AppData文件夹是一个系统文件夹&#xff0c;里面存储着临时文件&#xff0c;各种应用的自定义设置&#xff0c;快速启动文件等。近期有用户发现appdata\local\temp占用了大量的空间&#xff0c;那么该文件可以删除吗&#xff1f…...

Java手写聚类算法

Java手写聚类算法 1. 算法思维导图 以下是聚类算法的实现原理的思维导图&#xff0c;使用Mermanid代码表示&#xff1a; #mermaid-svg-AK9EgYRS38PkRJI4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-AK9EgYRS38…...

解密Java多线程中的锁机制:CAS与Synchronized的工作原理及优化策略

目录 CAS什么是CASCAS的应用ABA问题异常举例 Synchronized 原理基本特征加锁过程偏向锁轻量级锁重量级锁 其他优化操作锁消除锁粗化 CAS 什么是CAS CAS: 全称Compare and swap&#xff0c;字面意思:”比较并交换“&#xff0c;CAS涉及如下操作&#xff1a; 假设内存中的原数据…...

solid works草图绘制与设置零件特征的使用说明

&#xff08;1&#xff09;草图绘制 • 草图块 在 FeatureManager 设计树中&#xff0c;您可以隐藏和显示草图的单个块。您还可以查看块是欠定义 (-)、过定义 () 还是完全定义。 要隐藏和显示草图的单个块&#xff0c;请在 FeatureManager 设计树中右键单击草图块&#xff0c;…...

vue3使用router.push()页面跳转后,该页面不刷新问题

文章目录 原因分析最优解决 原因分析 这是一个常见问题&#xff0c;当使用push的时候&#xff0c;会向history栈添加一个新记录&#xff0c;这个时候&#xff0c;再添加一个完全相同的路由时&#xff0c;就不会再次刷新了 最优解决 在页面跳转时加上params参数时间 router.…...

如何理解数字工厂管理系统的本质

随着科技的飞速发展和数字化转型的推动&#xff0c;数字工厂管理系统逐渐成为工业4.0时代的重要工具。数字工厂系统旨在整合和优化工厂运营的各个环节&#xff0c;通过实时数据分析和处理&#xff0c;提升生产效率&#xff0c;降低成本&#xff0c;并增强企业的整体竞争力。为了…...

笔记1.3 数据交换

如何实现数据通过网络核心从源主机到达目的主机&#xff1f; 数据交换 交换网络&#xff1a; 动态转接动态分配传输资源 数据交换类型&#xff1a; &#xff08;1&#xff09;电路交换 &#xff08;2&#xff09;报文交换 &#xff08;3&#xff09;分组交换 电路交换的特…...

实时车辆行人多目标检测与跟踪系统(含UI界面,Python代码)

算法架构&#xff1a; 目标检测&#xff1a;yolov5 目标跟踪&#xff1a;OCSort其中&#xff0c; Yolov5 带有详细的训练步骤&#xff0c;可以根据训练文档&#xff0c;训练自己的数据集&#xff0c;及其方便。 另外后续 目标检测会添加 yolov7 、yolox&#xff0c;目标跟踪会…...

谷歌AI机器人Bard发布强大更新,支持插件功能并增强事实核查;全面整理高质量的人工智能、机器学习、大数据等技术资料

&#x1f989; AI新闻 &#x1f680; 谷歌AI机器人Bard发布强大更新&#xff0c;支持插件功能并增强事实核查 摘要&#xff1a;谷歌的人工智能聊天机器人Bard发布了一项重大更新&#xff0c;增加了对谷歌应用的插件支持&#xff0c;包括 Gmail、Docs、Drive 等&#xff0c;并…...

NI SCXI-1125 数字量控制模块

NI SCXI-1125 是 NI&#xff08;National Instruments&#xff09;生产的数字量控制模块&#xff0c;通常用于工业自动化和控制系统中&#xff0c;以进行数字输入和输出控制。以下是该模块的一些主要产品特点&#xff1a; 数字量输入&#xff1a;SCXI-1125 模块通常具有多个数字…...

链表oj题1(Leetcode)——移除链表元素,反转链表,链表的中间节点,

链表OJ 一&#xff0c;移除链表元素1.1分析1.2代码 二&#xff0c;找到链表的中间节点2.1分析2.2代码 三&#xff0c;反转链表3.1分析3.2代码 四&#xff0c;找到链表中倒数第k个节点4.1分析4.2代码 一&#xff0c;移除链表元素 移除链表元素 1.1分析 这里的删除要分成两种…...

【libuv】与uvgrtrp的_SSIZE_T_定义不同

libuv的 #if !defined(_SSIZE_T_) && !defined(_SSIZE_T_DEFINED) typedef intptr_t ssize_t;...

安卓ROM定制 修改必备常识-----初步了解system系统分区文件夹的基本含义 【二】

安卓修改rom 固件 修改GSI 移植rom 必备常识 lib--**so文件基本解析 一起来了解system目录相应文件的用途吧。&#xff08;rom版本不同里面的app也会不一样&#xff09; 简单打开img格式后缀文件 给大家说下最简单的方法提取img里面的文件&#xff0c;对于后缀img格式的文件可…...

GPT会统治人类吗

一 前言 花了大概两天时间看完《这就是ChatGPT》&#xff0c;触动还是挺大的&#xff0c;让我静下来&#xff0c;认真地想一想&#xff0c;是否真正理解了ChatGPT&#xff0c;又能给我们以什么样的启发。 二 思考 在工作和生活中&#xff0c;使用ChatGPT或文心一言&#xff0c;…...

win系统环境搭建(六)——Windows安装nginx

windows环境搭建专栏&#x1f517;点击跳转 win系统环境搭建&#xff08;六&#xff09;——Windows安装nginx 本系列windows环境搭建开始讲解如何给win系统搭建环境&#xff0c;本人所用系统是腾讯云服务器的Windows Server 2022&#xff0c;你可以理解成就是你用的windows10…...

Java中使用BigDecimal类相除保留两位小数

问题 遇到2个数相除&#xff0c;需要保留2位小数的结果。 解决 BigDecimal sum ...; BigDecimal yearValue ...;MathContext mathContext new MathContext(2, RoundingMode.DOWN); yearValue.divide(sum, mathContext);...

激光雷达在ADAS测试中的应用与方案

在科技高速发展的今天&#xff0c;汽车智能化已是必然的趋势&#xff0c;且自动驾驶汽车的研究也在世界范围内进行得如火如荼。而在ADAS测试与开发中&#xff0c;激光雷达以其高性能和高精度占据着非常重要的地位&#xff0c;它是ADAS测试与开发中不可缺少的组成。 一 激光雷达…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...