DeepSeek LeetCode 3753. 范围内总波动值 II Python3实现
这道题的核心是数位DP (Digit DP)，直接枚举区间内的每个数字会超时。代码实现可以直接参考 LeetCode 官方题解区或 GitHub 上的高票答案。
📝 问题回顾
· 波动值 (Waviness)：一个数字中峰（严格大于两边）和谷（严格小于两边）的总数。
· 规则：首尾数字不算；少于3位的数字波动值为0。
· 目标：返回区间 [num1, num2] 内所有数字波动值之和。
🧠 核心思路：数位DP (Digit DP)
利用前缀和思想 f(num) 计算 [0, num] 的总波动值，答案即为 f(num2) - f(num1 - 1)。
数位DP通过状态压缩避免枚举每个数字，核心DP状态通常包含：
· pos：当前处理到第几位。
· lastDigit / prevDigit：前一位或前两位的数字（用于判断峰谷）。
· lastDir：前两位数字的大小关系（上升/下降/相等）。
· tight：当前前缀是否和上限 num 的前缀完全一致（决定当前位上限）。
· started：是否已经开始填数字（用于处理前导零）。
💻 Python3 代码实现
```python
class Solution:
def totalWaviness(self, num1: int, num2: int) -> int:
# 辅助函数：计算 [0, num] 内所有数字的波动值之和
def count_upto(num: int) -> int:
if num < 100: # 少于3位，波动值均为0
return 0
digits = list(map(int, str(num)))
n = len(digits)
from functools import lru_cache
# 比较两个数字的大小关系，用于判断峰谷
# 返回: -1 下降, 0 相等, 1 上升
def cmp(a: int, b: int) -> int:
if a < b:
return 1
if a == b:
return 0
return -1
@lru_cache(None)
def dfs(pos: int, prev2: int, prev1: int, started: bool, tight: bool) -> (int, int):
# 返回: (从当前状态能构造出的数字个数, 这些数字的波动值总和)
if pos == n:
# 如果从未开始（即数字0），个数为1，波动值为0
return (1, 0) if started else (0, 0)
limit = digits[pos] if tight else 9
total_count = 0
total_waviness = 0
for d in range(0, limit + 1):
n_started = started or d != 0
n_tight = tight and (d == limit)
if not n_started:
# 仍然是前导零，prev1和prev2无意义，用 -1 占位
cnt, wav = dfs(pos + 1, -1, -1, False, n_tight)
else:
if not started:
# 刚结束前导零，当前是第一个有效数字，无法判断峰谷
cnt, wav = dfs(pos + 1, -1, d, True, n_tight)
else:
# 已有至少一个有效数字，可以尝试判断峰谷
add = 0
# 当 prev2 也存在时（即至少有3个有效数字），判断 prev1 是否为峰或谷
if prev2 != -1:
if (prev2 < prev1 > d) or (prev2 > prev1 < d):
add = 1
cnt, wav = dfs(pos + 1, prev1, d, True, n_tight)
wav += add * cnt # 当前位判断产生的波动值，贡献给所有后续构造出的数字
total_count += cnt
total_waviness += wav
return (total_count, total_waviness)
# 从最高位开始DFS，初始时未开始（started=False），处于受限状态（tight=True）
return dfs(0, -1, -1, False, True)[1]
# 利用前缀和思想，计算区间 [num1, num2] 的结果
return count_upto(num2) - count_upto(num1 - 1)
```
⏱️ 复杂度分析
· 时间复杂度：约为 O(log N * 10 * 状态数)，其中 N 是 num2。状态数（pos, prev1, prev2, started, tight）是常数级别，因此效率很高。
· 空间复杂度：O(状态数)，用于存储记忆化搜索的缓存。
✅ 测试示例
```python
sol = Solution()
print(sol.totalWaviness(120, 130)) # 输出: 3
print(sol.totalWaviness(198, 202)) # 输出: 3
print(sol.totalWaviness(4848, 4848)) # 输出: 2
```
这段代码通过数位DP高效地统计了所有数字的波动值总和，可以处理 num2 高达 10^15 的情况。