LeetCode 376 - 摆动序列

LeetCode 376 – 摆动序列

简单记录一下对题解的理解,下文一定不适合所有人

此题有 DP 和贪心两种解法,两种解法的代码是相同的,我的理解方式为贪心

以第一个示例 [1, 7, 4, 9, 2, 5] 为例,下图把整个数组放入坐标系,横坐标为数组下标,纵坐标为下标对应的值(图自 python3-一图胜千言

LeetCode 376 - 摆动序列

最后的目标是找到摆动序列(元素值上下振荡)的最大长度,而且并不要求连续

在遍历数组时,如果遵循定义,就将最大长度 +1 ,不遵循摆动序列定义的情况无非三种:

  1. 连续递增:以上图为例,元素 10 之前都遵循摆动序列的定义,但是到元素 13 时不遵循了(5 到 10 是递增的,10 到 13 也是递增的),这个时候可以直接退回到上一个递减元素(也就是元素 5),相当于跳过之前的递增序列(等同于删除了之前的递增元素,在图像上直接将 13 和 5 相连),摆动序列的长度也就可以直接在元素 5 的最大长度上 +1
  2. 连续递减:同上,直接退回到上一个递增元素,在它的最大长度基础上 +1
  3. (连续)相等:直接跳过,最大长度保持不变(相当于一个元素,可以直接在图像上表示为一个点)

所以,只要在一次遍历时维护两个记录了递增和递减序列长度的数组 up/down 即可

题目仅求最大值,所以只要保存数组中的最大值——即,将两个数组精简为两个变量

两个变量 up/down 本身已经具有了判断递增递减的功能,不需要额外的变量辅助判断增减状态:

  • 递增时,up 数值需要变化,down 的数值为上一个递减的最大值,up 在 down 的基础上 +1
  • 递减时,down 数值需要变化,up 的数值为上一个递增的最大值,down 在 up 的基础上 +1

最终,得到一个 O(n) 时间复杂度和 O(1) 空间复杂度的算法

C# 题解

public class Solution {
    public int WiggleMaxLength(int[] nums) {
    int n = nums.Length;

    int up = 1, down = 1;
    for (int i = 0; i < n - 1; i++) {
        if (nums[i + 1] > nums[i]) up = down + 1;
        else if (nums[i + 1] < nums[i]) down = up + 1;
    }

    return Math.Max(up, down);
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据