题目理解

波动值定义：

· 峰：数位 严格大于 其两个相邻数位
· 谷：数位 严格小于 其两个相邻数位
· 第一个和最后一个数位不能是峰或谷
· 少于3位的数字，波动值为0

示例：4848 中，第二个数位 8 是峰，第三个数位 4 是谷，波动值 = 2。

---

核心思路：前缀和 + 数位DP

直接枚举区间每个数字会超时（num 最大可达 10^15）。

核心技巧：

定义 f(n) = [0, n] 范围内所有数字的波动值之和
则区间 [num1, num2] 的答案 = f(num2) - f(num1 - 1)

这样只需实现计算 [0, n] 波动值之和的函数。

---

Java 实现（数位DP + 记忆化搜索）

```java
class Solution {
private int[] digits;
// dp[pos][pre2][pre][cnt][limit]
// pre2/pre: 10 表示"无前一位"（处理前导零）
private Long[][][][][] memo;

public long totalWaviness(long num1, long num2) {
return countUpTo(num2) - countUpTo(num1 - 1);
}

private long countUpTo(long n) {
if (n < 100) return 0; // 少于3位，波动值均为0
String s = String.valueOf(n);
digits = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
digits[i] = s.charAt(i) - '0';
}
// 维度: pos, pre2(0-10), pre(0-10), cnt(0-20), limit(0/1)
memo = new Long[digits.length][11][11][20][2];
return dfs(0, 10, 10, 0, true, true);
}

/**
* @param pos 当前处理到的位置
* @param pre2 前两位的数字（10表示不存在）
* @param pre 前一位的数字（10表示不存在）
* @param cnt 已经累计的波动值
* @param limit 是否受上界 n 的限制
* @param lead 是否仍处于前导零状态
*/
private long dfs(int pos, int pre2, int pre, int cnt, boolean limit, boolean lead) {
if (pos == digits.length) {
return cnt;
}

if (!limit && memo[pos][pre2][pre][cnt][lead ? 1 : 0] != null) {
return memo[pos][pre2][pre][cnt][lead ? 1 : 0];
}

int maxDigit = limit ? digits[pos] : 9;
long res = 0;

for (int d = 0; d <= maxDigit; d++) {
boolean newLimit = limit && (d == maxDigit);
boolean newLead = lead && (d == 0);
int newCnt = cnt;

// 只有当前不是前导零，且前面已经有两个有效数字时，才判断 pre 是否为峰/谷
if (!newLead && pre2 != 10 && pre != 10) {
if ((pre > pre2 && pre > d) || (pre < pre2 && pre < d)) {
newCnt++;
}
}

int newPre2 = newLead ? 10 : pre;
int newPre = newLead ? 10 : d;

res += dfs(pos + 1, newPre2, newPre, newCnt, newLimit, newLead);
}

if (!limit) {
memo[pos][pre2][pre][cnt][lead ? 1 : 0] = res;
}
return res;
}
}
```

---

代码详解

1. 状态设计

· pre2：前两位数字（用于判断 pre 是否为峰/谷）
· pre：前一位数字
· 用 10 表示"不存在"，因为数字范围是 0-9

2. 前导零处理

· lead = true 时，当前及之前所有位都是前导零（数字还未真正开始）
· 前导零不参与波动值计算

3. 判断峰/谷

当 pre2、pre、d 三个连续数位都存在时：

```java
if ((pre > pre2 && pre > d) || (pre < pre2 && pre < d)) {
newCnt++;
}
```

4. 记忆化条件

只有 !limit 时才能缓存，因为 limit=true 时可选数字范围因 n 而异。

---

复杂度分析

· 时间复杂度：O(len * 11 * 11 * 20 * 2 * 10) ≈ O(len * 24200)，len ≤ 16，常数级
· 空间复杂度：O(len * 11 * 11 * 20 * 2)