LeetCode 筆記 - 376. Wiggle Subsequence

題目在此 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
85
class 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

也許你也會想看看