DeepSeek LeetCode 3699. 锯齿形数组的总数 I Java实现

这道题的核心是动态规划 + 前缀和优化。因为数组的增减趋势必须交替（如 a<b>c<d），我们只需记录最后一个值和最后一步方向。

核心思路

· 状态定义：up[i] 表示最后一步为上升且以值 i 结尾的方案数；down[i] 同理为下降。
· 状态转移：
· 要形成新的上升（到 x），前一步必须是下降且结尾值 < x：newUp[x] = sum(down[0] + ... + down[x-1])。
· 要形成新的下降（到 x），前一步必须是上升且结尾值 > x：newDown[x] = sum(up[x+1] + ... + up[m-1])。
· 优化：用前缀和快速计算 newUp，用后缀和快速计算 newDown，避免遍历求和，将复杂度从 O(n·m²) 降至 O(n·m)。

---

Java 实现（空间优化版 O(m)）

```java
class Solution {
private static final int MOD = 1_000_000_007;

public int zigZagArrays(int n, int l, int r) {
int m = r - l + 1; // 取值个数

// 初始化长度为 1 的情况：每个值都可以作为起点
long[] up = new long[m];
long[] down = new long[m];
for (int i = 0; i < m; i++) {
up[i] = 1;
down[i] = 1;
}

// 重复 n-1 次，每次在末尾添加一个数
for (int len = 2; len <= n; len++) {
long[] newUp = new long[m];
long[] newDown = new long[m];

// 计算前缀和（用于 newUp）
long prefixSum = 0;
for (int x = 0; x < m; x++) {
newUp[x] = prefixSum; // sum of down[0..x-1]
prefixSum = (prefixSum + down[x]) % MOD;
}

// 计算后缀和（用于 newDown）
long suffixSum = 0;
for (int x = m - 1; x >= 0; x--) {
newDown[x] = suffixSum; // sum of up[x+1..m-1]
suffixSum = (suffixSum + up[x]) % MOD;
}

up = newUp;
down = newDown;
}

// 答案：所有 up 和 down 之和
long ans = 0;
for (int i = 0; i < m; i++) {
ans = (ans + up[i] + down[i]) % MOD;
}
return (int) ans;
}
}
```

另一种写法（滚动数组 + 前缀和数组）

使用 prefixSums 和 suffixSums 辅助计算：

```java
class Solution {
private static final int MOD = 1_000_000_007;

public int zigZagArrays(int n, int l, int r) {
int m = r - l + 1;
int[] up = new int[m];
int[] down = new int[m];
int[] prefixUp = new int[m + 1];
int[] prefixDown = new int[m + 1];

for (int j = 0; j < m; j++) {
up[j] = 1;
down[j] = 1;
prefixUp[j + 1] = (prefixUp[j] + up[j]) % MOD;
prefixDown[j + 1] = (prefixDown[j] + down[j]) % MOD;
}

for (int i = 1; i < n; i++) {
int[] newUp = new int[m];
int[] newDown = new int[m];
int[] newPrefixUp = new int[m + 1];
int[] newPrefixDown = new int[m + 1];

for (int j = 0; j < m; j++) {
// 上升：前一步下降且值 < j
newUp[j] = (j > 0) ? prefixDown[j] : 0; // prefixDown[j] = sum(down[0..j-1])
// 下降：前一步上升且值 > j
newDown[j] = (j + 1 < m) ? (prefixUp[m] - prefixUp[j + 1] + MOD) % MOD : 0;

newPrefixUp[j + 1] = (newPrefixUp[j] + newUp[j]) % MOD;
newPrefixDown[j + 1] = (newPrefixDown[j] + newDown[j]) % MOD;
}

up = newUp;
down = newDown;
prefixUp = newPrefixUp;
prefixDown = newPrefixDown;
}

return (prefixUp[m] + prefixDown[m]) % MOD;
}
}
```

复杂度

· 时间复杂度：O(n·m)
· 空间复杂度：O(m)