2026-04-05：范围内总波动值Ⅰ。用go语言，给定两个整数 num1 和 num2，考虑它们之间所有的整数（包含端点），即区间 [num1, num2]。 对区间内的每个整数，把它的每一位数字看

2026-04-05范围内总波动值Ⅰ。用go语言给定两个整数 num1 和 num2考虑它们之间所有的整数包含端点即区间 [num1, num2]。对区间内的每个整数把它的每一位数字看作一个“位置”。对某一位数字判断它是否构成“峰”或“谷”若这一位数字 严格大于 它左右相邻的两位数字则这位属于峰。若这一位数字 严格小于 它左右相邻的两位数字则这位属于谷。数字的第一位和最后一位不允许被算作峰或谷因为它们没有两侧相邻位。若该数字的位数少于 3即没有足够左右对比则它的“波动值”为 0。于是一个整数的波动值等于该数中所有峰的数量加上所有谷的数量。最后要求把区间 [num1, num2] 内每个整数的波动值加总返回这个总和。1 num1 num2 100000。输入 num1 120, num2 130。输出 3。解释在范围 [120, 130] 内120中间数位 2 是峰波动值 1。121中间数位 2 是峰波动值 1。130中间数位 3 是峰波动值 1。范围内所有其他数字的波动值均为 0。因此总波动值为 1 1 1 3。题目来自力扣3751。一、代码整体执行流程步骤1入口函数初始化程序从main函数开始输入区间num1120、num2130。调用totalWaviness(num1, num2)这是总结果的计算入口。步骤2区间差值计算总波动值核心逻辑totalWaviness函数执行计算f(num2)0到130所有数字的总波动值计算f(num1-1)0到119所有数字的总波动值最终结果 f(130) - f(119)直接得到区间[120,130]的总波动值。步骤3单边界总波动值计算f(n)函数以计算f(130)为例执行totalWavinessWithBound(130)基础判断130100不直接返回0进入数位DP计算获取数字位数130是3位数记为m3计算位数因子3位数的最高位因子是10010²用于拆分每一位数字初始化记忆化数组memo用途存储DP过程中重复计算的结果避免重复递归提升效率维度[位数][前一位数字][大小关系标记][是否受限]所有值初始化为-1标记未计算启动递归DP从数字的**最高位第0位**开始递归计算返回0到n的总波动值。步骤4数位DP递归核心逻辑dp函数这是计算波动值的核心递归遍历数字的每一位逐位枚举可能的数字记录状态并累加波动值递归终止条件遍历完所有位数到达最后一位的下一位返回当前波动值0当前数字个数1代表1个完整数字状态读取如果当前状态已经计算过非受限状态直接读取记忆化数组的结果不重复计算确定当前位可枚举的最大数字若受限tighttrue当前位不能超过原数字的对应位如130最高位只能枚举1若不受限当前位可以枚举0~9所有数字逐位枚举数字0~最大数字记录当前位数字作为下一位的「前一位数字」计算新的大小关系当前位数字 和 前一位数字 的大小对比小于/等于/大于/初始未知更新受限状态只有上一步受限且当前位取到最大值下一步才继续受限递归下一位计算后续所有位的总波动值和数字个数累加波动值根据「前后大小关系的变化」判断是否新增峰/谷每新增1个峰/谷就给所有后续数字的波动值1记忆化存储将非受限状态的计算结果存入memo数组方便后续复用返回结果返回当前状态下的总波动值和数字总个数。步骤5大小关系判断辅助函数getNewComparison判断当前位数字和前一位数字的大小关系小于/等于/大于初始状态无前一位标记为未知wavinessIncrease判断是否新增峰/谷——只有前一次是小于、当前是大于或前一次是大于、当前是小于严格交替才会产生1个峰/谷波动值1其余情况不增加。步骤6输出最终结果f(130) - f(119) 3程序打印结果3与题目示例一致。二、关键细节补充位数过滤代码中n≤100直接返回0因为≤100的数字位数3波动值恒为0记忆化优化memo数组避免了大量重复递归是数位DP高效的核心波动值统计规则严格按照「中间位、严格大于/小于、峰谷交替」统计首尾位不参与完全符合题目要求。三、时间复杂度分析核心计算单元数位DP的状态总数 位数 × 前一位数字(0~9) × 大小关系(4种) × 受限状态(2种)最大位数题目上限100000是6位数因此总状态数 6 × 10 × 4 × 2 480常数级递归次数每个状态仅计算1次逐位枚举数字最多10次常数总时间复杂度O(1)常数级。原因数字最大固定为6位所有计算量都是固定常数与输入数字大小无关。四、额外空间复杂度分析额外空间指除输入输出外程序运行中申请的内存主要空间memo记忆化数组大小为6 × 10 × 4 × 2 480个int64元素递归栈空间最大递归深度数字最大位数6层其他变量位数、因子、临时变量等均为常数级总额外空间复杂度O(1)常数级。总结执行过程区间差值法拆分计算 → 数位DP逐位枚举数字 → 状态记忆化优化 → 辅助函数判断峰谷 → 累加总波动值时间复杂度O(1)常数级固定计算量额外空间复杂度O(1)常数级固定内存占用。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[position][prev][comparison][tight]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}funcgetLength(nint64)int{length:0forn0{n/10length}returnlength}funcdp(memo[][][][]int64,nint64,factorint64,positionint,prevint,comparisonint,tightbool)(int64,int64){ifpositionlen(memo){return0,1}tightFlag:0if!tight{tightFlag1}iftightFlag1memo[position][prev][comparison][0]0{returnmemo[position][prev][comparison][0],memo[position][prev][comparison][1]}varnewWavinessint640varnewCountint640digit:int((n/factor)%10)maxDigit:digitif!tight{maxDigit9}ford:0;dmaxDigit;d{newPrev:d newComparison:getNewComparison(d,prev,comparison)newTight:tightddigit nextWav,nextCount:dp(memo,n,factor/10,position1,newPrev,newComparison,newTight)newWavinessnextWavint64(wavinessIncrease(comparison,newComparison))*nextCount newCountnextCount}iftightFlag1{memo[position][prev][comparison][0]newWaviness memo[position][prev][comparison][1]newCount}returnnewWaviness,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.Println(result)}Python完整代码如下# -*-coding:utf-8-*-classSolution:UNKNOWN0LESS1EQUAL2GREATER3deftotalWaviness(self,num1:int,num2:int)-int:returnself.totalWavinessWithBound(num2)-self.totalWavinessWithBound(num1-1)deftotalWavinessWithBound(self,n:int)-int:ifn100:return0mself.getLength(n)factor10**(m-1)# memo[position][prev][comparison] [waviness, count] for non-tight statesmemo[[[[-1,-1]for_inrange(4)]for_inrange(10)]for_inrange(m)]res,_self.dp(memo,n,factor,0,0,self.UNKNOWN,True)returnresdefgetLength(self,n:int)-int:length0whilen0:n//10length1returnlengthdefdp(self,memo,n:int,factor:int,position:int,prev:int,comparison:int,tight:bool):ifpositionlen(memo):return0,1ifnottightandmemo[position][prev][comparison][0]0:returnmemo[position][prev][comparison][0],memo[position][prev][comparison][1]newWaviness0newCount0digit(n//factor)%10maxDigitdigitiftightelse9fordinrange(maxDigit1):newPrevd newComparisonself.getNewComparison(d,prev,comparison)newTighttightand(ddigit)nextWav,nextCountself.dp(memo,n,factor//10,position1,newPrev,newComparison,newTight)newWavinessnextWavself.wavinessIncrease(comparison,newComparison)*nextCount newCountnextCountifnottight:memo[position][prev][comparison][0]newWaviness memo[position][prev][comparison][1]newCountreturnnewWaviness,newCountdefgetNewComparison(self,curr:int,prev:int,comparison:int)-int:ifcomparisonself.UNKNOWNandprev0:returnself.UNKNOWNifcurrprev:returnself.LESSelifcurrprev:returnself.EQUALelse:returnself.GREATERdefwavinessIncrease(self,comparison:int,newComparison:int)-int:if(comparisonself.LESSandnewComparisonself.GREATER)or\(comparisonself.GREATERandnewComparisonself.LESS):return1return0defmain():solSolution()num1120num2130resultsol.totalWaviness(num1,num2)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includecstringusingnamespacestd;constintUNKNOWN0;constintLESS1;constintEQUAL2;constintGREATER3;intgetLength(longlongn){intlength0;while(n0){n/10;length;}returnlength;}intgetNewComparison(intcurr,intprev,intcomparison){if(comparisonUNKNOWNprev0){returnUNKNOWN;}if(currprev){returnLESS;}elseif(currprev){returnEQUAL;}else{returnGREATER;}}intwavinessIncrease(intcomparison,intnewComparison){if((comparisonLESSnewComparisonGREATER)||(comparisonGREATERnewComparisonLESS)){return1;}return0;}// memo[position][prev][comparison][0] waviness, [1] countvectorvectorvectorvectorlonglongmemo;pairlonglong,longlongdp(longlongn,longlongfactor,intposition,intprev,intcomparison,booltight){if(positionmemo.size()){return{0,1};}inttightFlagtight?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);auto[nextWav,nextCount]dp(n,factor/10,position1,newPrev,newComparison,newTight);newWavinessnextWav(longlong)wavinessIncrease(comparison,newComparison)*nextCount;newCountnextCount;}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;}// 初始化 memomemo.assign(m,vectorvectorvectorlonglong(10,vectorvectorlonglong(4,vectorlonglong(2,-1))));auto[res,_]dp(n,factor,0,0,UNKNOWN,true);returnres;}longlongtotalWaviness(longlongnum1,longlongnum2){returntotalWavinessWithBound(num2)-totalWavinessWithBound(num1-1);}intmain(){longlongnum1120;longlongnum2130;longlongresulttotalWaviness(num1,num2);coutresultendl;return0;}