LeetCode 筆記 - 376. Wiggle Subsequence
這題是給定一個數列，請給出最長波動序列長度，就像一上一下這樣
解題思維
這題其實蠻有趣的，我自己就寫了幾種版本
基本上就是紀錄一上一下的長度，但值得注意的是計算的是序列
意思是有些數字可以被跳過然後繼續計算
也就是說如果剛好相反的波動，只要去掉開頭就可以接上
有了這個概念就差不多可以來實作了
程式碼
附上三種解題軌跡
如果只要看一種，可以看第一種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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if (size := len(nums)) <= 1:
return size
############################
result = 1
high = None
for i in range(1, size):
if nums[i - 1] > nums[i] and high != True:
result += 1
high = True
elif nums[i - 1] < nums[i] and high != False:
result += 1
high = False
return result
############################
dp_low = [1] * size
dp_high = [1] * size
for i in range(1, size):
if nums[i - 1] > nums[i]:
dp_low[i] = dp_high[i - 1] + 1
dp_high[i] = dp_high[i - 1]
elif nums[i - 1] < nums[i]:
dp_low[i] = dp_low[i - 1]
dp_high[i] = dp_low[i - 1] + 1
else:
dp_low[i] = dp_low[i - 1]
dp_high[i] = dp_high[i - 1]
return max(dp_low[-1], dp_high[-1])
############################
dp_length = [0] * size
dp_length[0] = 1
# 1 high point
# 0 all
# -1 low point
dp_type = [0] * size
result = 0
for i in range(1, size):
current_length = 1
current_type = 0
for ii in reversed(range(i)):
# 0. find the longest length
# 1. check if the point check the point type or not
if nums[ii] == nums[i]:
continue
if current_length >= dp_length[ii] + 1:
continue
update = False
if dp_type[ii] == 0:
update = True
elif dp_type[ii] == 1 and nums[ii] > nums[i]:
update = True
elif dp_type[ii] == -1 and nums[ii] < nums[i]:
update = True
if update:
current_length = dp_length[ii] + 1
if nums[ii] > nums[i]:
current_type = -1
else:
current_type = 1
break
dp_length[i] = current_length
dp_type[i] = current_type
result = max(result, dp_length[i])
return result