这道题要求统计区间 [l, r] 内所有相邻数位绝对差不超过 k 的整数个数。由于 r 最大可达 10^15暴力枚举不可行需要用数位 DP (Digit DP) 来解决。核心思路数位 DP 的核心是“按位构造”数字。我们定义一个递归函数 dfs(i, prev, tightLow, tightHigh)· i当前处理到第几位。· prev上一位的数字用 -1 表示还没有有效前一位以处理前导零。· tightLow / tightHigh表示前缀是否分别紧贴着下界 l 或上界 r。状态转移1. 递归出口处理完所有位数返回 1 表示找到一个好数。2. 确定当前位的可选范围· 下界tightLow ? low[i] : 0· 上界tightHigh ? high[i] : 93. 枚举并递归· 若当前仍处于前导零状态 (prev -1) 且选择 0则继续视为无前导零。· 否则检查当前位与 prev 的绝对差是否 k。TypeScript 实现typescriptfunction goodIntegers(l: number, r: number, k: number): number {// 将上下界补零对齐到相同长度方便数位DP处理const maxLen: number String(r).length;const lowStr: string String(l).padStart(maxLen, 0);const highStr: string String(r).padStart(maxLen, 0);const low: number[] lowStr.split().map(Number);const high: number[] highStr.split().map(Number);// 记忆化数组dp[i][prev1][tightLow][tightHigh]// prev 范围 -1 ~ 9加1偏移映射到 0 ~ 10const memo: Mapstring, number new Map();function dfs(i: number, prev: number, tightLow: boolean, tightHigh: boolean): number {if (i maxLen) {return 1; // 成功构造出一个好数}const key: string ${i},${prev 1},${tightLow},${tightHigh};if (memo.has(key)) {return memo.get(key)!;}// 确定当前位的可选范围const lo: number tightLow ? low[i] : 0;const hi: number tightHigh ? high[i] : 9;let ans: number 0;for (let digit lo; digit hi; digit) {const nextTightLow: boolean tightLow (digit lo);const nextTightHigh: boolean tightHigh (digit hi);// 处理前导零如果之前没有有效数字且当前填0则prev仍为-1if (prev -1 digit 0) {ans dfs(i 1, -1, nextTightLow, nextTightHigh);} else if (prev -1 || Math.abs(digit - prev) k) {// 第一个有效数字或差值满足条件ans dfs(i 1, digit, nextTightLow, nextTightHigh);}}memo.set(key, ans);return ans;}return dfs(0, -1, true, true);}复杂度分析· 时间复杂度O(maxLen * 10 * 2 * 2 * 10)即 O(log r * 10^2)对于 10^15 的量级绰绰有余。· 空间复杂度O(log r * 10 * 2 * 2)。
