LeetCode Wiggle Subsequence

LeetCode Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?


一个抖动序列是指第一个数比第二个数小,第二个数比第三个数大,第三个数比第四个数小...或者第一个数比第二个数大,后续类似的交替的大小关系。

现给定一个数组,要求数组中最长的抖动序列的长度。

首先可以用贪心的方法,每次我们选择数据的拐点(局部最大或最小值点)。比如下图中,第一选了A,后续一直是上升的趋势,则选择最大的D能获得更长的抖动序列长度。如果此时选较小的C的话,则下一个只能选H了,这样就漏了E和G。

贪心的代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		int ans = 1, i = 0, j = 1;
		bool up = false;
		while (j < n && nums[j] == nums[i])++j;
		if (nums[j] > nums[i])up = true;
		else up = false;
		while (j < n) {
			if (nums[j] > nums[i] && up) {
				++ans;
				up = false;
				while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
			}
			else if (nums[j] < nums[i] && !up) {
				++ans;
				up = true;
				while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
			}
			i = j++;
		}
		return ans;
	}
};

本代码提交AC,用时3MS。

还可以用动态规划的方法,假设up[i]表示第i个元素处于抖动序列的最后一个位置,且是上升的趋势时,前[0,i]的抖动子序列的最大长度。类似的,down[i]表示第i个元素处于抖动序列的最后一个位置,且是下降趋势时,前[0,i]的抖动子序列的最大长度。

则对于第i个元素,可以枚举所有i前面的元素j跳到i,如果nums[i]>nums[j],则i处于抖动序列的上升末尾,则从j到i构成的抖动序列中,j是处于下降趋势的,所以有up[i]=max(up[i],down[j]+1)。类似的,如果nums[i]<nums[j],则有down[i]=max(down[i],up[j]+1)。最后返回1+max(up[n-1],down[n-1])。

代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;

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

		return 1 + max(up[n - 1], down[n - 1]);
	}
};

本代码提交AC,用时6MS。

可以对上述代码优化。j无需枚举所有i前面的元素,而是i直接根据和前一个元素i-1的大小关系进行更新。如果nums[i]>nums[i-1],则i处于上升末端,所以i-1必须处于下降末端,有up[i]=down[i-1]+1,down[i]不变,即down[i]=down[i-1]。如果nums[i]<nums[i-1],则i处于下降末端,所以i-1必须处于上升末端,有down[i]=up[i-1]+1,up[i]不变,即up[i]=up[i-1]。如果nums[i]==nums[i-1],则up[i]和down[i]都不变,分别等于up[i-1]和down[i-1]。

为什么这里可以不用枚举所有i前面的元素了呢,因为上述三种情况中,只更新了该更新的,不能更新的情况都等于前一个元素的结果了,比如第一种情况更新了up[i],则down[i]保持了down[i-1]的值,所以后续如果要用到down[i-1]的值,也可以直接用down[i]的值了。

代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;

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

本代码提交AC,用时3MS。

还可以对上述代码进行空间的优化,因为up[i]和down[i]都只用到了前一个结果up[i-1]和down[i-1],所以只需保留前一个结果就行,不需要两个数组。代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;

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

		return max(up, down);
	}
};

本代码提交AC,用时0MS,是效率最好的一种解法了。

参考:https://leetcode.com/articles/wiggle-subsequence/,完整介绍了所有方法。

Leave a Reply

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