2026-04-07：范围内总波动值Ⅱ。用go语言，题意重新整理（纯文本描述）： 给定两个整数 num1 和 num2，它们定义一个闭区间 [num1, num2]。对区间内每个整数，都要计算它的“波

2026-04-07范围内总波动值Ⅱ。用go语言题意重新整理纯文本描述给定两个整数 num1 和 num2它们定义一个闭区间 [num1, num2]。对区间内每个整数都要计算它的“波动值”然后把所有整数的波动值加起来。“波动值”的计算规则如下1.把该整数按十进制拆成一串数位从左到右。2.对每个“中间数位”也就是除了最左和最右以外的数位看它与左右相邻数位的大小关系如果某一数位严格大于它的左右相邻数位那么这一个数位记为一个“峰”。如果某一数位严格小于它的左右相邻数位那么这一个数位记为一个“谷”。3.最左边的数位和最右边的数位不能被认定为峰或谷不参与峰谷计数。4.如果一个数字的位数少于 3 位那么它的波动值规定为 0。5.一个数字的波动值等于其中所有“峰”的数量加上所有“谷”的数量。最终要求计算区间 [num1, num2] 内所有数字的波动值之和并返回结果。1 num1 num2 1000000000000000。输入 num1 120, num2 130。输出 3。解释在范围 [120, 130] 内120中间数位 2 是峰波动值 1。121中间数位 2 是峰波动值 1。130中间数位 3 是峰波动值 1。范围内所有其他数字的波动值均为 0。因此总波动值为 1 1 1 3。题目来自力扣3753。解题过程分步详解一、先明确核心概念必须先看懂波动值数字位数 3波动值 0数字位数 ≥ 3只看中间数位排除第一位、最后一位峰中间数位严格大于左右两个邻居谷中间数位严格小于左右两个邻居波动值 峰的数量 谷的数量题目要求给定区间[num1, num2]求所有数字波动值的总和。数字范围极大1 ≤ num1 ≤ num2 ≤ 10^1515位不能暴力遍历每个数字。二、整体解题大框架最顶层思路因为数字范围到 10¹⁵暴力枚举会超时所以用数位动态规划数位DP解决。整体只有两步计算f(X) 从 0 到数字 X 的所有数字的总波动值最终答案 f(num2) - f(num1 - 1)区间和 前缀和相减三、分步拆解从 0 到 X 计算总波动值 f(X)步骤1特殊值快速判断如果数字 X小于 100最多两位那么所有数字波动值都是 0直接返回 0。步骤2拆分数字的位数与结构算出 X 是几位数比如 130 是 3 位数把 X 拆成每一位的数字1、3、0方便逐位处理准备好每一位的权重百位100十位10个位1步骤3数位DP核心准备记忆化搜索数位DP的作用不枚举每个数字而是按“位”枚举统计所有合法数字的总波动值。需要记录4个关键状态避免重复计算当前处理到第几位从左到右上一位的数字是什么0~9上一段的大小关系未知 / 上升 / 相等 / 下降是否紧贴数字上限决定当前位能填 0~9 还是只能填到 X 的对应位同时用记忆数组缓存已经算过的状态避免重复递归计算。四、数位DP递归过程逐位填数字统计总波动值这是最核心的计算流程我用纯文字描述1. 递归终止条件当所有位都填完时返回两个值总波动值0、有效数字个数1代表这是一个完整数字2. 记忆化剪枝如果当前状态没有被上限限制且之前已经计算过直接返回缓存的结果不再重复递归3. 确定当前位能填的数字范围如果紧贴上限当前位最大只能填 X 对应位的数字如果不紧贴上限当前位可以填 0~9 任意数字4. 枚举当前位的所有可能数字 d对每一个候选数字 d执行以下判断更新状态新的上一位数字 d新的大小关系对比 d 和 上一位数字小于/等于/大于新的上限紧贴状态只有之前紧贴且 d 等于上限数字时才保持紧贴递归计算下一位拿到下一位的两个结果下一段的总波动值下一段的有效数字个数累加当前位的贡献最关键波动值只会在中间数位产生当出现峰/谷时波动值 1规则先上升后下降 峰先下降后上升 谷每出现一次峰/谷就给所有后续数字都加上 1 点波动值累计总数总波动值 下一段波动值 当前位新增的波动值总数字个数 下一段数字个数5. 缓存结果记忆化如果当前状态不受上限限制把结果存入记忆数组下次直接用。6. 返回当前位的结果返回[当前总波动值当前总数字个数]五、完整流程总结从输入到输出以输入num1120num2130举例计算f(130)0~130 所有数字总波动值计算f(119)0~119 所有数字总波动值答案 f(130) - f(119) 3对应数字120(1)、121(1)、130(1)总和 3六、时间复杂度 额外空间复杂度1. 时间复杂度O(位数 × 10 × 4 × 2)位数最多 15 位10¹⁵10上一位数字 0~94大小关系未知/小于/等于/大于2紧贴上限状态是/否总状态数极少15 × 10 × 4 × 2 1200种每个状态只计算一次时间复杂度是常数级 O(1)极快。2. 额外空间复杂度O(位数 × 10 × 4 × 2)只用到一个记忆化数组存储 DP 状态数组大小固定最多 1200 个元素空间复杂度也是常数级 O(1)总结整体用数位DP 前缀和解决超大数字范围问题避免暴力枚举核心是逐位填数、记录状态、统计峰谷贡献时间复杂度O(1) 常数级空间复杂度O(1) 常数级完美支持 1~10¹⁵ 的范围要求Go完整代码如下packagemainimport(fmt)const(UNKNOWN0LESS1EQUAL2GREATER3)functotalWaviness(num1int64,num2int64)int64{returntotalWavinessWithBound(num2)-totalWavinessWithBound(num1-1)}functotalWavinessWithBound(nint64)int64{ifn100{return0}m:getLength(n)factor:int64(1)fori:1;im;i{factor*10}// 创建memo数组: [m][10][4][2]memo:make([][][][]int64,m)fori:0;im;i{memo[i]make([][][]int64,10)forj:0;j10;j{memo[i][j]make([][]int64,4)fork:0;k4;k{memo[i][j][k][]int64{-1,-1}}}}res:dp(memo,n,factor,0,0,UNKNOWN,true)returnres[0]}funcgetLength(nint64)int{length:0forn0{n/10length}returnlength}funcdp(memo[][][][]int64,nint64,factorint64,positionint,prevint,comparisonint,tightbool)[]int64{ifpositionlen(memo){return[]int64{0,1}}if!tightmemo[position][prev][comparison][0]0{return[]int64{memo[position][prev][comparison][0],memo[position][prev][comparison][1]}}varnewWavinessint640varnewCountint640digit:int(n/factor%10)maxDigit:9iftight{maxDigitdigit}ford:0;dmaxDigit;d{newPrev:d newComparison:getNewComparison(d,prev,comparison)newTight:tight(ddigit)varnextFactorint641iffactor1{nextFactorfactor/10}next:dp(memo,n,nextFactor,position1,newPrev,newComparison,newTight)newWavinessnext[0]int64(wavinessIncrease(comparison,newComparison))*next[1]newCountnext[1]}if!tight{memo[position][prev][comparison][0]newWaviness memo[position][prev][comparison][1]newCount}return[]int64{newWaviness,newCount}}funcgetNewComparison(currint,prevint,comparisonint)int{ifcomparisonUNKNOWNprev0{returnUNKNOWN}ifcurrprev{returnLESS}elseifcurrprev{returnEQUAL}else{returnGREATER}}funcwavinessIncrease(comparisonint,newComparisonint)int{if(comparisonLESSnewComparisonGREATER)||(comparisonGREATERnewComparisonLESS){return1}return0}funcmain(){num1:int64(120)num2:int64(130)result:totalWaviness(num1,num2)fmt.Printf(totalWaviness(%d, %d) %d\n,num1,num2,result)}Python完整代码如下# -*-coding:utf-8-*-deftotal_waviness(num1:int,num2:int)-int:returntotal_waviness_with_bound(num2)-total_waviness_with_bound(num1-1)deftotal_waviness_with_bound(n:int)-int:UNKNOWN,LESS,EQUAL,GREATER0,1,2,3ifn100:return0mget_length(n)factor10**(m-1)# 创建memo字典因为Python的多维列表初始化比较复杂fromfunctoolsimportlru_cachelru_cache(maxsizeNone)defdp(position:int,prev:int,comparison:int,tight:bool)-tuple:ifpositionm:return(0,1)new_waviness0new_count0digit(n//factor)%10ifposition0else(n//(10**(m-position-1)))%10max_digitdigitiftightelse9fordinrange(max_digit1):new_prevd new_comparisonget_new_comparison(d,prev,comparison,UNKNOWN)new_tighttightand(ddigit)next_waviness,next_countdp(position1,new_prev,new_comparison,new_tight)new_wavinessnext_wavinesswaviness_increase(comparison,new_comparison,LESS,GREATER)*next_count new_countnext_countreturn(new_waviness,new_count)result,_dp(0,0,UNKNOWN,True)returnresultdefget_length(n:int)-int:length0whilen0:n//10length1returnlengthiflength0else1defget_new_comparison(curr:int,prev:int,comparison:int,UNKNOWN:int)-int:LESS,EQUAL,GREATER1,2,3ifcomparisonUNKNOWNandprev0:returnUNKNOWNifcurrprev:returnLESSelifcurrprev:returnEQUALelse:returnGREATERdefwaviness_increase(comparison:int,new_comparison:int,LESS:int,GREATER:int)-int:if(comparisonLESSandnew_comparisonGREATER)or(comparisonGREATERandnew_comparisonLESS):return1return0defmain():num1120num2130resulttotal_waviness(num1,num2)print(ftotalWaviness({num1},{num2}) {result})if__name____main__:main()C完整代码如下#includeiostream#includevector#includecstringusingnamespacestd;constintUNKNOWN0;constintLESS1;constintEQUAL2;constintGREATER3;intgetNewComparison(intcurr,intprev,intcomparison){if(comparisonUNKNOWNprev0){returnUNKNOWN;}if(currprev){returnLESS;}elseif(currprev){returnEQUAL;}else{returnGREATER;}}intwavinessIncrease(intcomparison,intnewComparison){if((comparisonLESSnewComparisonGREATER)||(comparisonGREATERnewComparisonLESS)){return1;}return0;}intgetLength(longlongn){intlength0;while(n0){n/10;length;}returnlength;}// memo[position][prev][comparison][0] waviness, [1] countvectorlonglongdp(vectorvectorvectorvectorlonglongmemo,longlongn,longlongfactor,intposition,intprev,intcomparison,booltight){if(positionmemo.size()){return{0,1};}if(!tightmemo[position][prev][comparison][0]0){return{memo[position][prev][comparison][0],memo[position][prev][comparison][1]};}longlongnewWaviness0;longlongnewCount0;intdigit(n/factor)%10;intmaxDigittight?digit:9;for(intd0;dmaxDigit;d){intnewPrevd;intnewComparisongetNewComparison(d,prev,comparison);boolnewTighttight(ddigit);longlongnextFactor(factor1)?factor/10:1;vectorlonglongnextdp(memo,n,nextFactor,position1,newPrev,newComparison,newTight);newWavinessnext[0]wavinessIncrease(comparison,newComparison)*next[1];newCountnext[1];}if(!tight){memo[position][prev][comparison][0]newWaviness;memo[position][prev][comparison][1]newCount;}return{newWaviness,newCount};}longlongtotalWavinessWithBound(longlongn){if(n100){return0;}intmgetLength(n);longlongfactor1;for(inti1;im;i){factor*10;}// 创建memo数组: [m][10][4][2]vectorvectorvectorvectorlonglongmemo(m,vectorvectorvectorlonglong(10,vectorvectorlonglong(4,vectorlonglong(2,-1))));vectorlonglongresdp(memo,n,factor,0,0,UNKNOWN,true);returnres[0];}longlongtotalWaviness(longlongnum1,longlongnum2){returntotalWavinessWithBound(num2)-totalWavinessWithBound(num1-1);}intmain(){longlongnum1120;longlongnum2130;longlongresulttotalWaviness(num1,num2);couttotalWaviness(num1, num2) resultendl;return0;}