这道题的核心是数位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 代码实现pythonclass Solution:def totalWaviness(self, num1: int, num2: int) - int:# 辅助函数计算 [0, num] 内所有数字的波动值之和def count_upto(num: int) - int:if num 100: # 少于3位波动值均为0return 0digits 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 1if a b:return 0return -1lru_cache(None)def dfs(pos: int, prev2: int, prev1: int, started: bool, tight: bool) - (int, int):# 返回: (从当前状态能构造出的数字个数, 这些数字的波动值总和)if pos n:# 如果从未开始即数字0个数为1波动值为0return (1, 0) if started else (0, 0)limit digits[pos] if tight else 9total_count 0total_waviness 0for d in range(0, limit 1):n_started started or d ! 0n_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 1cnt, wav dfs(pos 1, prev1, d, True, n_tight)wav add * cnt # 当前位判断产生的波动值贡献给所有后续构造出的数字total_count cnttotal_waviness wavreturn (total_count, total_waviness)# 从最高位开始DFS初始时未开始startedFalse处于受限状态tightTruereturn 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(状态数)用于存储记忆化搜索的缓存。✅ 测试示例pythonsol Solution()print(sol.totalWaviness(120, 130)) # 输出: 3print(sol.totalWaviness(198, 202)) # 输出: 3print(sol.totalWaviness(4848, 4848)) # 输出: 2这段代码通过数位DP高效地统计了所有数字的波动值总和可以处理 num2 高达 10^15 的情况。
这道题的核心是数位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 代码实现pythonclass Solution:def totalWaviness(self, num1: int, num2: int) - int:# 辅助函数计算 [0, num] 内所有数字的波动值之和def count_upto(num: int) - int:if num 100: # 少于3位波动值均为0return 0digits 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 1if a b:return 0return -1lru_cache(None)def dfs(pos: int, prev2: int, prev1: int, started: bool, tight: bool) - (int, int):# 返回: (从当前状态能构造出的数字个数, 这些数字的波动值总和)if pos n:# 如果从未开始即数字0个数为1波动值为0return (1, 0) if started else (0, 0)limit digits[pos] if tight else 9total_count 0total_waviness 0for d in range(0, limit 1):n_started started or d ! 0n_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 1cnt, wav dfs(pos 1, prev1, d, True, n_tight)wav add * cnt # 当前位判断产生的波动值贡献给所有后续构造出的数字total_count cnttotal_waviness wavreturn (total_count, total_waviness)# 从最高位开始DFS初始时未开始startedFalse处于受限状态tightTruereturn 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(状态数)用于存储记忆化搜索的缓存。✅ 测试示例pythonsol Solution()print(sol.totalWaviness(120, 130)) # 输出: 3print(sol.totalWaviness(198, 202)) # 输出: 3print(sol.totalWaviness(4848, 4848)) # 输出: 2这段代码通过数位DP高效地统计了所有数字的波动值总和可以处理 num2 高达 10^15 的情况。
