DeepSeek LeetCode 3753. 范围内总波动值 II JavaScript实现

对于 LeetCode 3753 这道困难题，核心解法是数位 DP，配合前缀和技巧：F(num2) - F(num1-1)。以下是基于该思路的 JavaScript 实现。

```javascript
/**
* @param {number} num1
* @param {number} num2
* @return {number}
*/
var totalWaviness = function(num1, num2) {
const countUpTo = (x) => {
if (x < 100) return 0; // 少于3位数，波动值为0

const digits = String(x).split('').map(Number);
const n = digits.length;
// 记忆化缓存，key编码为字符串
const memo = new Map();

// pos: 当前处理位置, prev2: 前两位数字(-1表示不存在), prev1: 前一位数字(-1表示不存在), tight: 是否受到上界限制, started: 是否已经开始构造有效数字
const dfs = (pos, prev2, prev1, tight, started) => {
if (pos === n) {
return { count: 1, sum: 0 };
}

const key = `${pos},${prev2},${prev1},${tight},${started}`;
if (memo.has(key)) return memo.get(key);

const limit = tight ? digits[pos] : 9;
let totalCount = 0;
let totalSum = 0;

for (let d = 0; d <= limit; d++) {
const nextTight = tight && (d === limit);
const nextStarted = started || d !== 0;

// 仍然是前导零的情况：数字还未开始
if (!nextStarted) {
const res = dfs(pos + 1, -1, -1, nextTight, false);
totalCount += res.count;
totalSum += res.sum;
continue;
}

// 构造当前数字的三元组：prev2, prev1, d
let add = 0;
if (started && prev2 !== -1 && prev1 !== -1) {
// 判断 prev1 是否为峰或谷
if ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d)) {
add = 1;
}
}

const nextPrev2 = prev1;
const nextPrev1 = d;
const res = dfs(pos + 1, nextPrev2, nextPrev1, nextTight, true);

totalCount += res.count;
// 当前位对总和的贡献：如果当前构成波动，则后续每一种补全方式都贡献1
totalSum += res.sum + add * res.count;
}

const result = { count: totalCount, sum: totalSum };
memo.set(key, result);
return result;
};

// 返回 [0, x] 的总波动值
return dfs(0, -1, -1, true, false).sum;
};

// 前缀和思想：区间和 = F(num2) - F(num1-1)
return countUpTo(num2) - countUpTo(num1 - 1);
};
```

核心思路

1. 数位 DP + 容斥：分别计算 [0, num2] 和 [0, num1-1] 的总波动值，相减得到区间 [num1, num2] 的结果。
2. 状态设计：判断一个数字是否为峰/谷，需要知道它的前两位数字 prev2 和 prev1，因此将它们作为 DFS 的状态参数。此外还需：
· tight：是否紧贴上界，用于控制枚举上限。
· started：是否已经开始构造有效数字，用于处理前导零。
3. 贡献累加：在 DFS 过程中，每当我们确定一位数字 d 并发现它与 prev2、prev1 构成峰/谷时，不仅累加自身的 1，还要累加当前波动值 * 后续所有可能的补全方式数量，从而一次性统计所有合法数字的贡献。

复杂度

· 时间复杂度：O(log N * 10^2 * 2 * 2 * 10)，即 O(400 * log N)，其中 N 是 num2 的值。
· 空间复杂度：O(log N * 400)，用于记忆化缓存。