题目描述

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

例如, [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 
解释: 整个序列均为摆动序列。

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。

示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

进阶:
你能否用 O(n) 时间复杂度完成此题?

https://leetcode-cn.com/problems/wiggle-subsequence/

解法1 – 动态规划 O(n^2)

我们定义dp数组为dp[|nums|][2],dp[i][0]表示第i个元素作为较小元素构成的摆动序列最大长度;dp[i][1]表示第i个元素作为较大元素构成的摆动序列最大长度,且必须使用nums[i]。那么我们有dp[i][0] = dp[j][1]+1如果存在nums[j] > nums[i],否则dp[i][0]=1;dp[i][1] = dp[j][0]+1如果存在nums[j] < nums[i],否则dp[i][1]=1(0<=j<i)。

需要注意,当我们填充dp[i][0/1]时,我们向前寻找dp[j][1/0],不能找到第一个大于/小于nums[i]的元素后就停止,而是应该搜索到j = 0。因为有这样的case:

图1 dp数组更新过程

例如图1中的case,当i=4时nums[4]=0,当我们更新dp[4][0]时,我们不能只向前搜寻第一个大于nums[4]的位置。因为前面可能有更长的摆动序列,能够和0链接上,形成更长的摆动序列。在这个例子中,{53,1,3,1}与{1}都能和[0]形成摆动序列,但是我们要选最长的。

该方法的时间复杂度为O(n^2),空间复杂度为O(n)。全部代码如下:

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length < 1)
            return 0;
        int[][] dp = new int[nums.length][2]; // dp[i][0] means current elem as lower value, dp[i][1] means curr as higher value;
        int ans = 1;

        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = 1;
            dp[i][1] = 1;

            for (int j = i - 1; j >= 0; j--) {
                // curr as lower value
                if (nums[j] > nums[i]) {
                    dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
                }

                // curr as higher value
                if (nums[j] < nums[i]) {
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
            }
            ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));
        }

        return ans;
    }
}

解法2 – 动态规划 O(n)

我们还是使用动态规划,但是我们更改了dp数组的定义。我们定义数组dp[|nums|][2],dp[i][0]表示nums前i个数构成的摆动序列最大长度且序列最后一个数是较小的;dp[i][1]表示nums前i个数构成的摆动序列最大长度且序列最后一个数是较大的。那么有dp[i][0] = dp[i-1][1] + 1 如果 nums[i] < nums[i-1],否则dp[i][0] = dp[i-1][0];dp[i][1] = dp[i-1][0] + 1 如果nums[i] > nums[i-1],否则dp[i][1] = dp[i-1][1]。

我们换了dp数组的定义,那么dp[i]的数值只依赖于dp[i-1],我们就不需要对于每一个i向前回溯了。而解法1的定义是对于dp[i]我们必须使用nums[i]元素,那么我们就需要向前找比nums[i]小或者比nums[i]大的元素。

解法2的时间复杂度O(n),空间复杂度O(n)。全部代码如下:

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length < 1)
            return 0;
        int[][] dp = new int[nums.length][2];

        dp[0][0] = 1;
        dp[0][1] = 1;

        for (int i = 1; i < nums.length; i++) {
            dp[i][0] = (nums[i] < nums[i - 1] ? dp[i - 1][1] + 1 : dp[i - 1][0]);
            dp[i][1] = (nums[i] > nums[i - 1] ? dp[i - 1][0] + 1 : dp[i - 1][1]);
        }

        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }
}

我们观察到dp[i][0/1]只依赖于dp[i-1][0/1],这就允许我们将空间复杂度从O(n)优化到O(1)。我们定义两个变量lowerEndCnt,higherEndCnt来代表序列最后一个元素是较小的,所构成的最大长度;higherEndCnt表示序列最后一个元素是较大的,所构成的序列长度。

时间复杂度O(n),空间复杂度O(1)。全部代码如下:

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length < 1)
            return 0;

        int lowerEndCnt = 1;
        int higherEndCnt = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1])
                lowerEndCnt = higherEndCnt + 1;
            else if (nums[i] > nums[i - 1])
                higherEndCnt = lowerEndCnt + 1;
        }

        return Math.max(lowerEndCnt, higherEndCnt);
    }
}
pwrliang Algorithms, Dynamic Programming

Leave a Reply

Your email address will not be published. Required fields are marked *