Open youngyangyang04 opened 3 months ago
class Solution {
public int wiggleMaxLength(int[] nums) {
int diff = 0, last = 0, count = 1;
for (int i = 0; i < nums.length - 1; i++) {
diff = nums[i + 1] - nums[i];
if ((diff > 0 && last <= 0) || (diff < 0 && last >= 0)) {
count++;
last = diff;
}
}
return count;
}
}
i = 0, diff = 16, last = 0, 所以 count = 2, 摆动序列 [1,17]
i = 1, diff = -12, last = 16, 所以 count = 3, 摆动序列 [1,17,5]
i = 2, diff = 5, last = -12, 所以 count = 4, 摆动序列 [1,17,5,10]
i = 3, diff = 3, last = 5, 继续遍历
i = 4, diff = 2, last = 5, 继续遍历
i = 5, diff = -5, last = 5, 所以 count = 5, 摆动序列 [1,17,5,10,10]
i = 6, diff = -5, last = -5, 继续遍历
i = 7, diff = 11, last = -5, 所以 count = 6, 摆动序列 [1,17,5,10,10,16]
i = 8, diff = -8, last = 11, 所以 count = 7, 摆动序列 [1,17,5,10,10,16,8]
遍历数组,利用result栈来储存满足“摆动性”的值,且利用result栈顶的两个值来判断当前值,如果当前值满足“摆动性”则入栈,如果不满足则替换栈顶元素,以确保不错过“局部波动”,最后输出result的长度。缺点是增加了空间复杂度,python代码如下 根据迭代法稍加改动即可得到递归法,将其看作一个深度为len(nums)的树的遍历,缺点是利用了额外的递归栈空间
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) == 1:
return 1
result = []
result.append(nums[0])
# 始终保持前两个数字不同
start = 1
while start < len(nums) and nums[start] == result[-1]:
start += 1
if start < len(nums):
result.append(nums[start])
# 迭代法
for i in range(start + 1, len(nums)):
if result[-1] - result[-2] > 0:
if nums[i] >= result[-1]:
result[-1] = nums[i]
else:
result.append(nums[i])
elif result[-1] - result[-2] < 0:
if nums[i] <= result[-1]:
result[-1] = nums[i]
else:
result.append(nums[i])
return len(result)
https://www.programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html