• Leetcode376. 摆动序列

    Every day a Leetcode

    题目来源：376. 摆动序列

    解法1：动态规划

    约定：

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

    状态数组：

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

    最终的状态转移方程为：

    在这里插入图片描述

    最终的答案即为 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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    结果：

    在这里插入图片描述

    复杂度分析：

    时间复杂度：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 &nums)
//     {
//         // 特判
//         if (nums.size() <= 1)
//             return nums.size();
//         int n = nums.size();
//         // 状态数组
//         // up[i]：表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度
//         vector up(n + 1, 0);
//         // down[i]：表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度
//         vector 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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    结果：

    在这里插入图片描述

    解法2：贪心

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

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

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

    代码：

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

// @lc code=start

// 动态规划

// class Solution
// {
// public:
//     int wiggleMaxLength(vector &nums)
//     {
//         // 特判
//         if (nums.size() <= 1)
//             return nums.size();
//         int n = nums.size();
//         // 状态数组
//         // up[i]：表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度
//         vector up(n + 1, 0);
//         // down[i]：表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度
//         vector 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 &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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100

    结果：

    在这里插入图片描述

    复杂度分析：

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

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

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

    代码：

    // 贪心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;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    结果：

    在这里插入图片描述

    复杂度分析：

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

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

  • 相关阅读:
    Linux操作系统 - 进程
    多实例数据库备份脚本 mysql
    【Golang开发面经】B站（两轮技术面）
    算法---螺旋矩阵
    jenkins、sonarqube相关配置
    E. Iva & Pav -前缀和 + 二分 +位运算
    风力等级划分
    中南林业科技大学javaweb实验报告
    UI设计师都能做什么，UI设计都有哪几个职业方向
    中科大计网学习记录笔记（十二）：TCP 套接字编程
  • 原文地址：https://blog.csdn.net/ProgramNovice/article/details/132762514