LeetCode 每日一题 2026/6/1-2026/6/7

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

6/1 2144. 打折购买糖果的最小开销

免费的越大越好
排序 购买最大和第二大的 可以免费获得第三大的 以此类推

defminimumCost(cost):""" :type cost: List[int] :rtype: int """cost.sort(reverse=True)ans=0foriinrange(len(cost)):ifi%3!=2:ans+=cost[i]returnans

6/2 3633. 最早完成陆地和水上游乐设施的时间 I

枚举“陆地 i + 水上 j”的所有组合，并计算两种顺序的完成时间取最小：
land -> water
water -> land
所有组合中的最小值就是答案

defearliestFinishTime(landStartTime,landDuration,waterStartTime,waterDuration):""" :type landStartTime: List[int] :type landDuration: List[int] :type waterStartTime: List[int] :type waterDuration: List[int] :rtype: int """ans=float("inf")foriinrange(len(landStartTime)):land_finish=landStartTime[i]+landDuration[i]forjinrange(len(waterStartTime)):# 先玩陆地 i，再玩水上 jfinish1=max(waterStartTime[j],land_finish)+waterDuration[j]# 先玩水上 j，再玩陆地 iwater_finish=waterStartTime[j]+waterDuration[j]finish2=max(landStartTime[i],water_finish)+landDuration[i]best=finish1iffinish1<finish2elsefinish2ifbest<ans:ans=bestreturnans

6/3 3635. 最早完成陆地和水上游乐设施的时间 II

陆地项目 i：开始时间 A[i]，时长 B[i]
水上项目 j：开始时间 C[j]，时长 D[j]
总完成时间有两种顺序：
1.先陆地后水上：
T1(i, j) = max(C[j], A[i] + B[i]) + D[j]
2.先水上后陆地：
T2(i, j) = max(A[i], C[j] + D[j]) + B[i]
目标是最小化 min(T1, T2)。可转为分别求两种顺序的全局最小，再取较小者：
min_{i,j} min(T1, T2) = min( min_{i,j} T1, min_{i,j} T2 )
先看 T1：
固定 j 后，T1 = D[j] + max(C[j], A[i] + B[i])
其中 i 只出现在 A[i] + B[i]，记 minLandFinish = min_i (A[i] + B[i])，
则 min_i max(C[j], A[i] + B[i]) = max(C[j], minLandFinish)。
所以：
min_{i,j} T1 = min_j ( D[j] + max(C[j], minLandFinish) )
同理 T2：
记 minWaterFinish = min_j (C[j] + D[j])，
则：
min_{i,j} T2 = min_i ( B[i] + max(A[i], minWaterFinish) )
最终答案：
min( min_j(D[j] + max(C[j], minLandFinish)),
min_i(B[i] + max(A[i], minWaterFinish)) )

defearliestFinishTime(landStartTime,landDuration,waterStartTime,waterDuration):""" :type landStartTime: List[int] :type landDuration: List[int] :type waterStartTime: List[int] :type waterDuration: List[int] :rtype: int """n=len(landStartTime)m=len(waterStartTime)min_land_finish=float("inf")foriinrange(n):v=landStartTime[i]+landDuration[i]ifv<min_land_finish:min_land_finish=v min_water_finish=float("inf")forjinrange(m):v=waterStartTime[j]+waterDuration[j]ifv<min_water_finish:min_water_finish=v best_land_then_water=float("inf")forjinrange(m):finish=(waterStartTime[j]ifwaterStartTime[j]>min_land_finishelsemin_land_finish)+waterDuration[j]iffinish<best_land_then_water:best_land_then_water=finish best_water_then_land=float("inf")foriinrange(n):finish=(landStartTime[i]iflandStartTime[i]>min_water_finishelsemin_water_finish)+landDuration[i]iffinish<best_water_then_land:best_water_then_land=finishreturnbest_land_then_waterifbest_land_then_water<best_water_then_landelsebest_water_then_land

6/4 3751. 范围内总波动值 I

对区间 [num1, num2] 内每个数字 x，单独计算其“波动值”再累加
设一个数字的十进制位数组为 digits：
首位和末位不能成为峰/谷
对每个中间位 i（1 <= i <= n-2）：
若 digits[i] > digits[i-1] 且 digits[i] > digits[i+1]，是峰值
若 digits[i] < digits[i-1] 且 digits[i] < digits[i+1]，是谷值
满足其一就把波动值 +1
位数小于 3 的数字波动值为 0

deftotalWaviness(num1,num2):""" :type num1: int :type num2: int :rtype: int """defwaviness(x):digits=[int(ch)forchinstr(x)]n=len(digits)ifn<3:return0cnt=0foriinrange(1,n-1):mid=digits[i]left=digits[i-1]right=digits[i+1]if(mid>leftandmid>right)or(mid<leftandmid<right):cnt+=1returncnt ans=0forxinrange(num1,num2+1):ans+=waviness(x)returnans

6/5 3753. 范围内总波动值 II

定义前缀函数 f(n)：表示区间 [0, n] 内所有数字的波动值之和
最终答案是 f(num2) - f(num1 - 1)
用数位 DP 计算 f(n)。按从高位到低位构造数字，状态为
pos：当前处理到第几位
tight：前面是否与 n 的前缀完全相同（决定当前位上限）
started：是否已经开始构造有效数字（处理前导零）
prev1：已构造数字的最后一位
prev2：已构造数字的倒数第二位
当新填入一位 d 时，只有“上一位 prev1”可能在此刻被判定为峰/谷
峰：prev1 > prev2 且 prev1 > d
谷：prev1 < prev2 且 prev1 < d
一旦判定，把该贡献 +1，然后继续递归
递归返回二元组 (sumW, cnt)：
sumW：该状态下所有合法补全的总波动值
cnt：该状态下合法补全数量
若当前位形成了一个新峰/谷（extra 为 0/1），则要对所有后续补全都生效
sumW += childSum + extra * childCnt
pos 到末尾时返回 (0, 1)（构成一个完整数字）。
位数 < 3 的数字自然不会产生贡献，因为没有位置满足“左右邻居都存在”

deftotalWaviness(num1,num2):""" :type num1: int :type num2: int :rtype: int """fromfunctoolsimportlru_cache NONE=10# 哨兵：表示不存在该位（还没有足够多的有效数字）defcalc_upto(n):ifn<=0:return0s=str(n)L=len(s)@lru_cache(maxsize=None)defdfs(pos,tight,started,prev1,prev2):ifpos==L:return(0,1)up=ord(s[pos])-ord('0')iftightelse9total_sum=0total_cnt=0fordinrange(up+1):ntight=1if(tightandd==up)else0ifnotstartedandd==0:child_sum,child_cnt=dfs(pos+1,ntight,0,NONE,NONE)total_sum+=child_sum total_cnt+=child_cntcontinueifnotstarted:# 第一个有效数字，尚无法形成峰/谷child_sum,child_cnt=dfs(pos+1,ntight,1,d,NONE)total_sum+=child_sum total_cnt+=child_cntelse:# 已有至少 1 位有效数字，新加入 d 后可判断旧的 prev1 是否为峰/谷extra=0ifprev2!=NONE:if(prev1>prev2andprev1>d)or(prev1<prev2andprev1<d):extra=1child_sum,child_cnt=dfs(pos+1,ntight,1,d,prev1)total_sum+=child_sum+extra*child_cnt total_cnt+=child_cntreturn(total_sum,total_cnt)returndfs(0,1,0,NONE,NONE)[0]returncalc_upto(num2)-calc_upto(num1-1)

6/6

6/7