摆动序列

发表于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

LeetCode每日一题，376. Wiggle Subsequence

先看题目描述

rEvmgH.png

大意就是给定一个数组，让我们判断其中摆动序列的最大长度，当一个序列满足其中相邻元素的差值交替为正值和负值时，我们就称其为摆动序列

算法和思路

贪心算法

首先可以证明一定存在某个最长摆动序列，其中含有数组的第一个元素，这个通过反证法可以证明

假定目前摆动序列中最后一个数是 nums[i]，那么往摆动序列中添加下一个数的贪心策略是：

  • 若 nums[i + 1] > nums[i]，则找出接下来的最长递增子序列 [i+1, i+2，…, i+k]，满足 nums[i + 1] <= nums[i + 2] <= … <= nums[i + k]，然后将 nums[i + k] 添加到摆动序列最后
  • 若 nums[i + 1 < nums[i]，则找出接下来的最长递减子序列 [i+1, i+2，…, i+k]，满足 nums[i + 1] >= nums[i + 2] >= … >= nums[i + k]，然后将 nums[i + k] 添加到摆动序列最后
  • 若 nums[i + 1] 与 nums[i] 相等，则跳过该数

算法源码

贪心算法

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
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int res = 1;
        int pre = nums[0];
        for (int i = 1; i < len; ) {
            if (nums[i] < pre) {
                while (i < len && nums[i] <= nums[i - 1]) {
                    i++;
                }
                pre = nums[i - 1];
                res++;
            } else if (nums[i] > pre) {
                while (i < len && nums[i] >= nums[i - 1]) {
                    i++;
                }
                pre = nums[i - 1];
                res++;
            } else {
                i++;
            }
        }
        return res;
    }
}

这题自己的第一反应就是用贪心做，后来看题解，发现也可以用动态规划做，下面是题解实现的动态规划代码

动态规划

每当我们选择一个元素作为摆动序列的一部分时，这个元素要么是上升的，要么是下降的，这取决于前一个元素的大小。那么列出状态表达式为：

  • up[i] 表示以前 i 个元素中的某一个为结尾的最长的「上升摆动序列」的长度

  • down[i] 表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度

状态转移方程为：

rVphlD.png

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int[] up = new int[n];
        int[] down = new int[n];
        up[0] = down[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up[i] = Math.max(up[i - 1], down[i - 1] + 1);
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                up[i] = up[i - 1];
                down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
            } else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }
        return Math.max(up[n - 1], down[n - 1]);
    }
}