Leetcode376. 摆动序列

这篇具有很好参考价值的文章主要介绍了Leetcode376. 摆动序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Every day a Leetcode

题目来源:376. 摆动序列

解法1:动态规划

约定:

  1. 某个序列被称为「上升摆动序列」,当且仅当该序列是摆动序列,且最后一个元素呈上升趋势。
  2. 某个序列被称为「下降摆动序列」,当且仅当该序列是摆动序列,且最后一个元素呈下降趋势。
  3. 特别地,对于长度为 1 的序列,它既是「上升摆动序列」,也是「下降摆动序列」。
  4. 序列中的某个元素被称为「峰」,当且仅当该元素两侧的相邻元素均小于它。
  5. 序列中的某个元素被称为「谷」,当且仅当该元素两侧的相邻元素均大于它。
  6. 特别地,对于位于序列两端的元素,只有一侧的相邻元素小于或大于它,我们也称其为「峰」或「谷」。
  7. 对于序列中既非「峰」也非「谷」的元素,我们称其为「过渡元素」。

状态数组:

  1. up[i]:表示以前 i 个元素中的某一个为结尾的最长的「上升摆动序列」的长度。
  2. down[i]:表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。

最终的状态转移方程为:

Leetcode376. 摆动序列,Every day a leetcode,leetcode,算法,数据结构,动态规划,贪心

最终的答案即为 up[n−1] 和 down[n−1] 中的较大值,其中 n 是序列的长度。

代码:

/*
 * @lc app=leetcode.cn id=376 lang=cpp
 *
 * [376] 摆动序列
 */

// @lc code=start
class Solution
{
public:
    int wiggleMaxLength(vector<int> &nums)
    {
        // 特判
        if (nums.size() <= 1)
            return nums.size();
        int n = nums.size();
        // 状态数组
        // up[i]:表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度
        vector<int> up(n + 1, 0);
        // down[i]:表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度
        vector<int> down(n + 1, 0);
        // 初始化
        // 对于长度为1的序列,它既是「上升摆动序列」,也是「下降摆动序列」
        up[1] = down[1] = 1;
        // 状态转移
        for (int i = 2; i <= n; i++)
        {
            if (nums[i - 1] > nums[i - 2])
            {
                up[i] = max(up[i - 1], down[i - 1] + 1);
                down[i] = down[i - 1];
            }
            else if (nums[i - 1] < nums[i - 2])
            {
                up[i] = up[i - 1];
                down[i] = max(up[i - 1] + 1, down[i - 1]);
            }
            else
            {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }
        return max(up[n], down[n]);
    }
};
// @lc code=end

结果:

Leetcode376. 摆动序列,Every day a leetcode,leetcode,算法,数据结构,动态规划,贪心

复杂度分析:

时间复杂度:O(n),其中 n 是序列的长度。我们只需要遍历该序列一次。

空间复杂度:O(n),其中 n 是序列的长度。我们需要开辟两个长度为 n 的数组。

空间优化

代码:

/*
 * @lc app=leetcode.cn id=376 lang=cpp
 *
 * [376] 摆动序列
 */

// @lc code=start

// 动态规划

// class Solution
// {
// public:
//     int wiggleMaxLength(vector<int> &nums)
//     {
//         // 特判
//         if (nums.size() <= 1)
//             return nums.size();
//         int n = nums.size();
//         // 状态数组
//         // up[i]:表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度
//         vector<int> up(n + 1, 0);
//         // down[i]:表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度
//         vector<int> down(n + 1, 0);
//         // 初始化
//         // 对于长度为1的序列,它既是「上升摆动序列」,也是「下降摆动序列」
//         up[1] = down[1] = 1;
//         // 状态转移
//         for (int i = 2; i <= n; i++)
//         {
//             if (nums[i - 1] > nums[i - 2])
//             {
//                 up[i] = max(up[i - 1], down[i - 1] + 1);
//                 down[i] = down[i - 1];
//             }
//             else if (nums[i - 1] < nums[i - 2])
//             {
//                 up[i] = up[i - 1];
//                 down[i] = max(up[i - 1] + 1, down[i - 1]);
//             }
//             else
//             {
//                 up[i] = up[i - 1];
//                 down[i] = down[i - 1];
//             }
//         }
//         return max(up[n], down[n]);
//     }
// };

// 动态规划-空间优化

class Solution
{
public:
    int wiggleMaxLength(vector<int> &nums)
    {
        // 特判
        if (nums.size() <= 1)
            return nums.size();
        int n = nums.size();
        int up = 1, down = 1;
        // 状态转移
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > nums[i - 1])
                up = max(up, down + 1);
            else if (nums[i] < nums[i - 1])
                down = max(down, up + 1);
        }
        return max(up, down);
    }
};
// @lc code=end

结果:

Leetcode376. 摆动序列,Every day a leetcode,leetcode,算法,数据结构,动态规划,贪心

解法2:贪心

观察这个序列可以发现,我们不断地交错选择「峰」与「谷」,可以使得该序列尽可能长。证明非常简单:如果我们选择了一个「过渡元素」,那么在原序列中,这个「过渡元素」的两侧有一个「峰」和一个「谷」。不失一般性,我们假设在原序列中的出现顺序为「峰」「过渡元素」「谷」。如果「过渡元素」在选择的序列中小于其两侧的元素,那么「谷」一定没有在选择的序列中出现,我们可以将「过渡元素」替换成「谷」;同理,如果「过渡元素」在选择的序列中大于其两侧的元素,那么「峰」一定没有在选择的序列中出现,我们可以将「过渡元素」替换成「峰」。这样一来,我们总可以将任意满足要求的序列中的所有「过渡元素」替换成「峰」或「谷」。并且由于我们不断地交错选择「峰」与「谷」的方法就可以满足要求,因此这种选择方法就一定可以达到可选元素数量的最大值。

这样,我们只需要统计该序列中「峰」与「谷」的数量即可(注意序列两端的数也是「峰」或「谷」),但需要注意处理相邻的相同元素。

在实际代码中,我们记录当前序列的上升下降趋势。每次加入一个新元素时,用新的上升下降趋势与之前对比,如果出现了「峰」或「谷」,答案加一,并更新当前序列的上升下降趋势。

代码:

/*
 * @lc app=leetcode.cn id=376 lang=cpp
 *
 * [376] 摆动序列
 */

// @lc code=start

// 动态规划

// class Solution
// {
// public:
//     int wiggleMaxLength(vector<int> &nums)
//     {
//         // 特判
//         if (nums.size() <= 1)
//             return nums.size();
//         int n = nums.size();
//         // 状态数组
//         // up[i]:表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度
//         vector<int> up(n + 1, 0);
//         // down[i]:表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度
//         vector<int> down(n + 1, 0);
//         // 初始化
//         // 对于长度为1的序列,它既是「上升摆动序列」,也是「下降摆动序列」
//         up[1] = down[1] = 1;
//         // 状态转移
//         for (int i = 2; i <= n; i++)
//         {
//             if (nums[i - 1] > nums[i - 2])
//             {
//                 up[i] = max(up[i - 1], down[i - 1] + 1);
//                 down[i] = down[i - 1];
//             }
//             else if (nums[i - 1] < nums[i - 2])
//             {
//                 up[i] = up[i - 1];
//                 down[i] = max(up[i - 1] + 1, down[i - 1]);
//             }
//             else
//             {
//                 up[i] = up[i - 1];
//                 down[i] = down[i - 1];
//             }
//         }
//         return max(up[n], down[n]);
//     }
// };

// 动态规划-空间优化

// class Solution
// {
// public:
//     int wiggleMaxLength(vector<int> &nums)
//     {
//         // 特判
//         if (nums.size() <= 1)
//             return nums.size();
//         int n = nums.size();
//         int up = 1, down = 1;
//         // 状态转移
//         for (int i = 1; i < n; i++)
//         {
//             if (nums[i] > nums[i - 1])
//                 up = max(up, down + 1);
//             else if (nums[i] < nums[i - 1])
//                 down = max(down, up + 1);
//         }
//         return max(up, down);
//     }
// };

// 贪心

class Solution
{
public:
    int wiggleMaxLength(vector<int> &nums)
    {
        // 特判
        if (nums.size() <= 1)
            return nums.size();
        int n = nums.size();
        int preDiff = nums[1] - nums[0];
        int ans = preDiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++)
        {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && preDiff <= 0) || (diff < 0 && preDiff >= 0))
            {
                ans++;
                preDiff = diff;
            }
        }
        return ans;
    }
};
// @lc code=end

结果:

Leetcode376. 摆动序列,Every day a leetcode,leetcode,算法,数据结构,动态规划,贪心

复杂度分析:

时间复杂度:O(n),其中 n 是序列的长度。我们只需要遍历该序列一次。

空间复杂度:O(1)。我们只需要常数空间来存放若干变量。文章来源地址https://www.toymoban.com/news/detail-707215.html

第二种贪心思路:统计变化次数

代码:

// 贪心2

class Solution
{
public:
    int wiggleMaxLength(vector<int> &nums)
    {
        // 特判
        if (nums.size() <= 1)
            return nums.size();
        int n = nums.size();
        int direction = 0; //-1表示下降,1表示上升
        int count = 0;     // 变化次数
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > nums[i - 1])
            {
                if (direction != 1)
                {
                    direction = 1;
                    count++;
                }
            }
            else if (nums[i] < nums[i - 1])
            {
                if (direction != -1)
                {
                    direction = -1;
                    count++;
                }
            }
        }
        // 因为统计的是变化的次数,最终的结果是序列的长度,所以需要+1
        return count + 1;
    }
};

结果:

Leetcode376. 摆动序列,Every day a leetcode,leetcode,算法,数据结构,动态规划,贪心

复杂度分析:

时间复杂度:O(n),其中 n 是序列的长度。我们只需要遍历该序列一次。

空间复杂度:O(1)。我们只需要常数空间来存放若干变量。

到了这里,关于Leetcode376. 摆动序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Day31 贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和

    什么是贪心 贪心的本质是选择每一阶段的局部最优,从而达到全局最优 。 这么说有点抽象,来举一个例子: 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最

    2024年01月19日
    浏览(43)
  • 算法 贪心1 || 455.分发饼干 376. 摆动序列 53. 最大子数组和

    什么是贪心:贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 但是贪心没有套路,做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。 很容易想到,把孩子的胃口和饼干大小都排序,都从最小值开始遍历。如果最小的饼干无法满足最

    2023年04月16日
    浏览(46)
  • LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)

    贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。 感觉像

    2024年02月09日
    浏览(50)
  • 摆动序列——力扣376

    题目描述 贪心

    2024年02月13日
    浏览(33)
  • 代码随想录27|455.分发饼干,376. 摆动序列,53. 最大子序和

    链接地址 链接地址 链接地址

    2024年02月11日
    浏览(42)
  • 算法刷题Day 31 分发饼干+摆动序列+最大子序列和

    分发饼干其实有很多种写法,但是下面这种贪心的解法是最好理解,也最好解释的 我的其他解法 贪心算法 这道题用贪心算法要考虑的细节有很多。 动态规划 有点难(甚至涉及到了线段树),等后面二刷的时候再来学好了 暴力解法 超时了 贪心算法 贪心算法的代码写起来简

    2024年02月15日
    浏览(42)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(46)
  • 【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :首先我们要知道后序遍历数组的最后一个元素必然是根节点,然后根据根节点在中序遍历数组中的位置进行划分,得到根节点的左右子树遍历数组,以此递归。当然这里有一个前提

    2024年02月10日
    浏览(39)
  • 算法题:摆动序列(贪心算法解决序列问题)

    这道题是一道贪心算法题,如果前两个数是递增,则后面要递减,如果不符合则往后遍历,直到找到符合的。(完整题目附在了最后) 代码如下: 完整题目: 376. 摆动序列 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为  摆动序列 。 第一个差(如果

    2024年02月07日
    浏览(60)
  • 摆动序列【贪心算法】

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

    2024年02月11日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包