Skip to content

Commit b82fc66

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0376
No.0376.Wiggle Subsequence
1 parent 9058394 commit b82fc66

File tree

6 files changed

+361
-114
lines changed

6 files changed

+361
-114
lines changed

‎solution/0300-0399/0376.Wiggle Subsequence/README.md

Lines changed: 176 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -62,16 +62,33 @@
6262

6363
<!-- 这里可写通用的实现逻辑 -->
6464

65-
动态规划。
65+
**方法一：动态规划**
6666

67-
设 up 表示以前 i 个元素中的某一个元素结尾的最长上升摆动序列的长度，down 表示以前 i 个元素中的某一个元素结尾的最长下降摆动序列的长度。初始 `up = 1`, `down = 1`。
67+
我们定义 $f[i][0]$ 表示以第 $i$ 个元素结尾，且最后两个元素的差为负数的最长摆动序列的长度，定义 $f[i][1]$ 表示以第 $i$ 个元素结尾，且最后两个元素的差为正数的最长摆动序列的长度。初始时 $f[0][0]=1$, $f[0][1]=1$。
6868

69-
从数组下标 1 开始遍历：
69+
我们可以得到状态转移方程：
7070

71-
- 若 `nums[i] > nums[i - 1]`，则需要更新最长上升摆动序列的长度：`up = max(up, down + 1)`
72-
- 若 `nums[i] < nums[i - 1]`，则需要更新最长下降摆动序列的长度：`down = max(down, up + 1)`
71+
$$
72+
f[i][0] = \max(f[j][1] + 1), \quad nums[i] < nums[j], j \in [0, i - 1]
73+
$$
7374

74-
最后返回 `max(up, down)` 即可。
75+
$$
76+
f[i][1] = \max(f[j][0] + 1), \quad nums[i] > nums[j], j \in [0, i - 1]
77+
$$
78+
79+
答案为 $f[i][0]$ 和 $f[i][1]$ 中的最大值。
80+
81+
时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。
82+
83+
**方法二：动态规划（优化）**
84+
85+
我们定义变量 $f$ 和 $g$ 分别表示当前最后两个元素的差为负数和正数的最长摆动序列的长度。初始时 $f = 1$, $g = 1$。
86+
87+
遍历数组 $nums[1,..]$，如果当前元素 $nums[i]$ 大于前一个元素 $nums[i - 1]$，则 $f = \max(f, g + 1)$，否则如果当前元素 $nums[i]$ 小于前一个元素 $nums[i - 1]$，则 $g = \max(g, f + 1)$。
88+
89+
遍历结束后，将 $f$ 和 $g$ 中的最大值作为答案返回。
90+
91+
时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。
7592

7693
<!-- tabs:start -->
7794

@@ -82,13 +99,32 @@
8299
```python
83100
class Solution:
84101
def wiggleMaxLength(self, nums: List[int]) -> int:
85-
up = down = 1
86-
for i in range(1, len(nums)):
87-
if nums[i] > nums[i - 1]:
88-
up = max(up, down + 1)
89-
elif nums[i] < nums[i - 1]:
90-
down = max(down, up + 1)
91-
return max(up, down)
102+
n = len(nums)
103+
f = [[1] * 2 for _ in range(n)]
104+
ans = 1
105+
for i in range(1, n):
106+
for j in range(i):
107+
d = nums[i] - nums[j]
108+
if d == 0:
109+
continue
110+
if d < 0:
111+
f[i][0] = max(f[i][0], f[j][1] + 1)
112+
if d > 0:
113+
f[i][1] = max(f[i][1], f[j][0] + 1)
114+
ans = max(ans, *f[i])
115+
return ans
116+
```
117+
118+
```python
119+
class Solution:
120+
def wiggleMaxLength(self, nums: List[int]) -> int:
121+
f = g = 1
122+
for a, b in pairwise(nums):
123+
if a < b:
124+
f = max(f, g + 1)
125+
if a > b:
126+
g = max(g, f + 1)
127+
return max(f, g)
92128
```
93129

94130
### **Java**
@@ -98,35 +134,46 @@ class Solution:
98134
```java
99135
class Solution {
100136
public int wiggleMaxLength(int[] nums) {
101-
int up = 1, down = 1;
102-
for (int i = 1; i < nums.length; ++i) {
103-
if (nums[i] > nums[i - 1]) {
104-
up = Math.max(up, down + 1);
105-
} else if (nums[i] < nums[i - 1]) {
106-
down = Math.max(down, up + 1);
137+
int n = nums.length;
138+
int[][] f = new int[n][2];
139+
int ans = 1;
140+
f[0][0] = 1;
141+
f[0][1] = 1;
142+
for (int i = 1; i < n; ++i) {
143+
for (int j = 0; j < i; ++j) {
144+
int d = nums[i] - nums[j];
145+
if (d == 0) {
146+
continue;
147+
}
148+
if (d < 0) {
149+
f[i][0] = Math.max(f[i][0], f[j][1] + 1);
150+
}
151+
if (d > 0) {
152+
f[i][1] = Math.max(f[i][1], f[j][0] + 1);
153+
}
107154
}
155+
ans = Math.max(ans, Math.max(f[i][0], f[i][1]));
108156
}
109-
return Math.max(up, down);
157+
return ans;
110158
}
111159
}
112160
```
113161

114-
### **TypeScript**
115-
116-
```ts
117-
function wiggleMaxLength(nums: number[]): number {
118-
let up = 1,
119-
down = 1;
120-
for (let i = 1; i < nums.length; ++i) {
121-
let prev = nums[i - 1],
122-
cur = nums[i];
123-
if (cur > prev) {
124-
up = Math.max(up, down + 1);
125-
} else if (cur < prev) {
126-
down = Math.max(down, up + 1);
162+
```java
163+
class Solution {
164+
public int wiggleMaxLength(int[] nums) {
165+
int f = 1, g = 1;
166+
for (int i = 1; i < nums.length; ++i) {
167+
int d = nums[i] - nums[i - 1];
168+
if (d < 0) {
169+
f = Math.max(f, g + 1);
170+
}
171+
if (d > 0) {
172+
g = Math.max(g, f + 1);
173+
}
127174
}
175+
return Math.max(f, g);
128176
}
129-
return Math.max(up, down);
130177
}
131178
```
132179

@@ -136,15 +183,47 @@ function wiggleMaxLength(nums: number[]): number {
136183
class Solution {
137184
public:
138185
int wiggleMaxLength(vector<int>& nums) {
139-
int up = 1, down = 1;
186+
int n = nums.size();
187+
int f[n][2];
188+
memset(f, 0, sizeof(f));
189+
int ans = 1;
190+
f[0][0] = 1;
191+
f[0][1] = 1;
192+
for (int i = 1; i < n; ++i) {
193+
for (int j = 0; j < i; ++j) {
194+
int d = nums[i] - nums[j];
195+
if (d == 0) {
196+
continue;
197+
}
198+
if (d < 0) {
199+
f[i][0] = max(f[i][0], f[j][1] + 1);
200+
}
201+
if (d > 0) {
202+
f[i][1] = max(f[i][1], f[j][0] + 1);
203+
}
204+
}
205+
ans = max({ans, f[i][0], f[i][1]});
206+
}
207+
return ans;
208+
}
209+
};
210+
```
211+
212+
```cpp
213+
class Solution {
214+
public:
215+
int wiggleMaxLength(vector<int>& nums) {
216+
int f = 1, g = 1;
140217
for (int i = 1; i < nums.size(); ++i) {
141-
if (nums[i] > nums[i - 1]) {
142-
up = max(up, down + 1);
143-
} else if (nums[i] < nums[i - 1]) {
144-
down = max(down, up + 1);
218+
int d = nums[i] - nums[i - 1];
219+
if (d < 0) {
220+
f = max(f, g + 1);
221+
}
222+
if (d > 0) {
223+
g = max(g, f + 1);
145224
}
146225
}
147-
return max(up, down);
226+
return max(f, g);
148227
}
149228
};
150229
```
@@ -153,15 +232,46 @@ public:
153232

154233
```go
155234
func wiggleMaxLength(nums []int) int {
156-
up, down := 1, 1
157-
for i := 1; i < len(nums); i++ {
158-
if nums[i] > nums[i-1] {
159-
up = max(up, down+1)
160-
} else if nums[i] < nums[i-1] {
161-
down = max(down, up+1)
235+
n := len(nums)
236+
f := make([][2]int, n)
237+
f[0][0], f[0][1] = 1, 1
238+
ans := 1
239+
for i := 1; i < n; i++ {
240+
for j := 0; j < i; j++ {
241+
d := nums[i] - nums[j]
242+
if d < 0 {
243+
f[i][0] = max(f[i][0], f[j][1]+1)
244+
}
245+
if d > 0 {
246+
f[i][1] = max(f[i][1], f[j][0]+1)
247+
}
248+
}
249+
ans = max(ans, max(f[i][0], f[i][1]))
250+
}
251+
return ans
252+
}
253+
254+
func max(a, b int) int {
255+
if a > b {
256+
return a
257+
}
258+
return b
259+
}
260+
```
261+
262+
```go
263+
func wiggleMaxLength(nums []int) int {
264+
f, g := 1, 1
265+
for i, x := range nums[1:] {
266+
d := x - nums[i]
267+
if d < 0 {
268+
f = max(f, g+1)
269+
}
270+
if d > 0 {
271+
g = max(g, f+1)
162272
}
163273
}
164-
return max(up, down)
274+
return max(f, g)
165275
}
166276

167277
func max(a, b int) int {
@@ -172,6 +282,25 @@ func max(a, b int) int {
172282
}
173283
```
174284

285+
### **TypeScript**
286+
287+
```ts
288+
function wiggleMaxLength(nums: number[]): number {
289+
let up = 1,
290+
down = 1;
291+
for (let i = 1; i < nums.length; ++i) {
292+
let prev = nums[i - 1],
293+
cur = nums[i];
294+
if (cur > prev) {
295+
up = Math.max(up, down + 1);
296+
} else if (cur < prev) {
297+
down = Math.max(down, up + 1);
298+
}
299+
}
300+
return Math.max(up, down);
301+
}
302+
```
303+
175304
### **...**
176305

177306
```

0 commit comments

Comments
 (0)