题目理解波动值定义· 峰数位 严格大于 其两个相邻数位· 谷数位 严格小于 其两个相邻数位· 第一个和最后一个数位不能是峰或谷· 少于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 记忆化搜索javaclass 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位波动值均为0String 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-92. 前导零处理· lead true 时当前及之前所有位都是前导零数字还未真正开始· 前导零不参与波动值计算3. 判断峰/谷当 pre2、pre、d 三个连续数位都存在时javaif ((pre pre2 pre d) || (pre pre2 pre d)) {newCnt;}4. 记忆化条件只有 !limit 时才能缓存因为 limittrue 时可选数字范围因 n 而异。---复杂度分析· 时间复杂度O(len * 11 * 11 * 20 * 2 * 10) ≈ O(len * 24200)len ≤ 16常数级· 空间复杂度O(len * 11 * 11 * 20 * 2)
题目理解波动值定义· 峰数位 严格大于 其两个相邻数位· 谷数位 严格小于 其两个相邻数位· 第一个和最后一个数位不能是峰或谷· 少于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 记忆化搜索javaclass 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位波动值均为0String 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-92. 前导零处理· lead true 时当前及之前所有位都是前导零数字还未真正开始· 前导零不参与波动值计算3. 判断峰/谷当 pre2、pre、d 三个连续数位都存在时javaif ((pre pre2 pre d) || (pre pre2 pre d)) {newCnt;}4. 记忆化条件只有 !limit 时才能缓存因为 limittrue 时可选数字范围因 n 而异。---复杂度分析· 时间复杂度O(len * 11 * 11 * 20 * 2 * 10) ≈ O(len * 24200)len ≤ 16常数级· 空间复杂度O(len * 11 * 11 * 20 * 2)
