文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布

摆动序列，也能贪心

摆动序列 力扣题目链接：https://leetcode-cn.com/problems/wiggle-subsequence 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。...少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。...示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。...相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？ 来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？...设dp状态dp[i][0]，表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度 设dp状态dp[i][1]，表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度 则转移方程为： dp[i][0

73510
    • 您找到你想要的搜索结果了吗？
    是的
    没有找到

    摆动序列

    1 题目描述 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。...给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。...摆动序列 本题要求通过从原始序列中删除一些(也可以不删除)元素来获得子序列，剩下的元素保持其原始顺序。 相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢?...来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢?...整体最优:整个序列有最多的局部峰值，从而达到最长摆动序列。 局部最优推出全局最优，并举不出反例，那么试试贪心!

    40530

    贪心算法：摆动序列

    摆动序列 题目链接：https://leetcode-cn.com/problems/wiggle-subsequence/ 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。...少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。...示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。...相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？ 来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？ 用示例二来举例，如图所示： ?...376.摆动序列 「局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值」。 「整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列」。

    92620

    摆动序列（贪心 & 动态规划）

    题目 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。...例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。...给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。...示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。...2.2 动态规划 up表示到当前数为止是上升的摆动数列长度； down表示到当前数为止是下降的摆动数列长度； if(nums[i] > nums[i-1]) up = down+1; else if

    1.3K10

    每日算法系列【LeetCode 376】摆动序列

    题目描述 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。...例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 [6,-3,5,-7,3] 是正负交替出现的。...相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。...给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。...示例1 输入： [1,7,4,9,2,5] 输出： 6 解释： 整个序列均为摆动序列。

    50910

    leetcode每日一题：376.摆动序

    ：最长的摆动子序列长度，子序列即要求保证数值的相对位置，摆动序列的定义：差值呈现正负交替的情况 难度：中等 标签：贪心、动态规划 注意： 长度小于 2 的时候，也是摆动序列 最好能用 O(N) 的时间复杂度解决...，并且保证这些摆动子序列连接后仍然是摆动序列，就能得到最长的摆动序列。...因为从上面我们的解法可以看出来，我们的序列其实是增、减序列的组合，当有连续增或减时，当再次出来反向序列，这个反向序列一定可以连接前面的摆动序列并组成新的摆动序列。...+m+n] 又是一个摆动序列。...从前面的假设我们可以知道这个序列满足： # 因为 [j, j+m] 单调递减，而 [i, j] 是摆动序列 # 即从 j+1 开始由于单调减，导致不能继续组合成摆动序列 # 因此摆动序列最后两个元素满足

    53820

    动态规划-376.摆动序列-力扣(LeetCode)

    一、题目解析 看着题目上的解释或许有点难以理解，这里一图流 只要形似上图的都可以是摆动序列，如左图，且仅含一个元素和两个元素的也算摆动序列，如右图 二、算法原理 1、状态表示 根据经验我们都是以i位置为结尾时...，最长摆动子序列的长度 但是根据我们下面的题目分析，我们可以知道最后一个位置存在两种情况 f[i]表示：以i位置为结尾时，最后一个呈“上升”趋势的，最长摆动子序列 g[i]表示：一i位置为结尾时，最后一个呈...“下降”趋势的，最长摆动子序列 2、状态转移方程 f[i]是以上升为结尾，所以前一个状态为下降 f[i]->长度为1时->f[i]=1 f[i]->长度大于1是->nums[j]摆动序列 - 力扣（LeetCode） 三、代码示例 class Solution { public: int wiggleMaxLength(vector& nums) {

    12010
    点击加载更多

    相关资讯

    热门标签

    更多标签

    活动推荐

      运营活动

      活动名称
      广告关闭

      腾讯云开发者

      扫码关注腾讯云开发者

      扫码关注腾讯云开发者

      领取腾讯云代金券

      热门产品

      热门推荐

      更多推荐

      Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

      深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

      腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号

      领券