0%

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:

1
2
3
4
5
6
7
8
9
10
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?

题目地址:leetcode Wiggle Subsequencey

题意:给定一个数组,让你求最大摆动序列长度。摆动序列定义为序列中任意相邻的三个数中abc,均有 a < b , b >c 或者a>b b<c

思路:

方法一,看到这个就想到和LIS差不多,迅速的DP一下,1A,

设dp[i] 为以i结尾的最大摆动序列长度,sign[i]为i这个数比之前的大还是小(大为1,小-1,初始0),更新条件如下:

  • dp[j] + 1 > dp[i] and (sign[j] > 0 and nums[i] < nums[j] or sign[j] < 0 and nums[i] > nums[j] or sign[j] == 0 and nums[i] != nums[j]):

很好的写出相应的python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
n = len(nums)
dp, sign = [1] * n, [0] * n
for i in range(1, n):
for j in range(i - 1, -1, -1):
if dp[j] + 1 > dp[i] and (
sign[j] > 0 and nums[i] < nums[j] or
sign[j] < 0 and nums[i] > nums[j] or
sign[j] == 0 and nums[i] != nums[j]):
sign[i] = 1 if nums[i] > nums[j] else -1
dp[i] = dp[j] + 1
return max(dp)

 

方法二 虽然dp简单,但其复杂度O(n^2)并不是本题最佳解法。

摇摆序列要求升高,降低,升高。。。

或者降低,升高,降低。。。

那么我们只要找出数组中的“拐点” 即可 举个例子:

4 5 6  3 2 1这几个数中,4为起点,那么5和6中,我们肯定选6啊~因为之后的数要求小于5,小于5的必定也小于6 比如改为4 5 6 5,之前要是选5就没办法继续往下了。。

总之就是选最小的和选最大的(也就是拐点) 保证不丢最优解。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
int ans = 1;
for (int i = 1, j = 0; i < n; j = i,i++) {
if (nums[j] < nums[i]) {
ans++;
while (i + 1 < n && nums[i] <= nums[i + 1]) i++;
}
else if (nums[j] > nums[i]) {
ans++;
while (i + 1 < n && nums[i] >= nums[i + 1]) i++;
}
}
return ans;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0) return 0;
int n = nums.length;
int ans = 1;
for (int i = 1, j = 0; i < n; j = i,i++) {
if (nums[j] < nums[i]) {
ans++;
while (i + 1 < n && nums[i] <= nums[i + 1]) i++;
}
else if (nums[j] > nums[i]) {
ans++;
while (i + 1 < n && nums[i] >= nums[i + 1]) i++;
}
}
return ans;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
n = len(nums)
ans, i, j, = 1, 1, 0
while i < n:
if nums[j] < nums[i]:
ans += 1
while i + 1 < n and nums[i + 1] >= nums[i]:
i += 1
elif nums[j] > nums[i]:
ans += 1
while i + 1 < n and nums[i + 1] <= nums[i]:
i += 1
i, j = i + 1, i
return ans

 

本题是leetcode 376 Wiggle Subsequence题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~