【LeetCode 】在下标间移动的最小代价贪心前缀和 O(nq) 多解法超详解析目录问题描述示例分析思路过程解法一暴力建图 最短路不可行解法二观察单调性与贪心策略解法三前缀和优化最终最优解算法详解Step1计算 closest 数组Step2定义方向代价Step3前缀和预处理Step4O(1) 回答每个查询完整代码实现复杂度分析单调性正确性证明测试与验证总结与扩展1. 问题描述给你一个严格递增的整数数组nums。对于每个下标x定义closest\(x\)为使得abs\(nums\[x\] \- nums\[y\]\)最小化的相邻下标。特殊规则如果左右相邻下标差值相同则选择更小的下标。你拥有两种移动方式任意瞬移从下标x移动到任意下标y代价为abs\(nums\[x\] \- nums\[y\]\)。捷径移动从下标x移动到closest\(x\)固定代价为1。给定二维查询数组queries每个查询\[li, ri\]代表从下标li移动到ri求每次移动的最小总代价。约束条件2 \lt; nums\.length \lt; 10^5\-10^9 \lt; nums\[i\] \lt; 10^9nums严格递增1 \lt; queries\.length \lt; 10^50 \lt; li, ri \lt; nums\.length2. 示例分析示例 1输入nums [-5,-2,3], queries [[0,2],[2,0],[1,2]] 输出[6,2,5]预处理得到closest \[1, 0, 1\]查询\[0,2\]0→1捷径代价1 1瞬移→2代价5总代价 6查询\[2,0\]2→1代价1 1→0代价1全程捷径总代价 2查询\[1,2\]直接瞬移代价5优于捷径绕路总代价 5示例 2输入nums [0,2,3,9], queries [[3,0],[1,2],[2,0]] 输出[4,1,3]预处理得到closest \[1, 2, 1, 2\]查询\[3,0\]3→2(1) 2→1(1) 1瞬移→0(2)总代价 4查询\[1,2\]直接捷径移动代价 1查询\[2,0\]2→1(1) 1瞬移→0(2)总代价 3核心规律最优路径不存在折返始终沿起点到终点的方向单调移动。3. 思路过程3.1 解法一暴力建图 最短路不可行思路原理将数组每个下标视为图的节点构建两类边全连接瞬移边任意节点i→j代价为数值绝对差捷径边i→closest\(i\)固定代价 1对每个查询使用 Dijkstra 算法求解单点最短路。致命缺陷全连接边数量为O ( n 2 ) O(n^2)O(n2)无法存储与遍历n 、 q ≤ 10 5 n、q \le 10^5n、q≤105单次 DijkstraO ( n log ⁡ n ) O(n\log n)O(nlogn)总复杂度爆炸超时结论暴力最短路仅适用于教学理解无法通过大数据测试。3.2 解法二观察单调性与贪心策略核心观察数组严格递增数值差满足三角不等式折返移动会额外增加数值代价捷径的1点代价节省无法弥补折返损耗。因此最优路径一定单调不折返起点l \lt; r只向右移动起点l \gt; r只向左移动贪心策略相邻两点移动时永远选择最小代价若当前节点捷径指向前进方向代价为1否则使用瞬移代价数值差值3.3 解法三前缀和优化最终最优解基于贪心单调性预处理左右方向相邻最小代价再通过前缀和数组预处理区间代价最终实现O(1) 单次查询整体复杂度O ( n q ) O(nq)O(nq)完美适配 1e5 极限数据。4. 算法详解4.1 Step1计算 closest 数组根据题目规则遍历每个下标求解最近相邻下标首位下标i0无左邻居closest\[0\] 1末位下标in\-1无右邻居closest\[n\-1\] n\-2中间下标对比左右差值左差值≤右差值选左否则选右差值相等选小下标nlen(nums)closest[0]*n closest[0]1closest[n-1]n-2foriinrange(1,n-1):left_diffnums[i]-nums[i-1]right_diffnums[i1]-nums[i]ifleft_diffright_diff:closest[i]i-1else:closest[i]i14.2 Step2定义方向代价定义两个代价数组存储相邻两点的最小移动代价R\[i\]从i向右走到i\1的最小代价L\[i\]从i向左走到i\-1的最小代价代价规则捷径指向目标下标则代价为1否则为数值差值。# 向右代价 R[i]: i - i1R[0]*(n-1)foriinrange(n-1):ifclosest[i]i1:R[i]1else:R[i]nums[i1]-nums[i]# 向左代价 L[i]: i - i-1L[0]*nforiinrange(1,n):ifclosest[i]i-1:L[i]1else:L[i]nums[i]-nums[i-1]4.3 Step3前缀和预处理构建前缀和数组快速求解任意区间的累计最小代价prefR\[i\]前i个向右代价的前缀和用于查询右行区间prefL\[i\]前i个向左代价的前缀和用于查询左行区间prefR[0]*nforiinrange(n-1):prefR[i1]prefR[i]R[i]prefL[0]*nforiinrange(1,n):prefL[i]prefL[i-1]L[i]4.4 Step4O(1) 回答每个查询根据起点终点大小关系直接通过前缀和差值计算答案l \lt; r右行代价prefR\[r\] \- prefR\[l\]l \gt; r左行代价prefL\[l\] \- prefL\[r\]l r无需移动代价 05. 完整代码实现classSolution:defminCost(self,nums:list[int],queries:list[list[int]])-list[int]:# ©leetcodenlen(nums)ifn1:return[0]*len(queries)# Step1: 预处理closest数组closest[0]*n closest[0]1closest[-1]n-2foriinrange(1,n-1):left_diffnums[i]-nums[i-1]right_diffnums[i1]-nums[i]ifleft_diffright_diff:closest[i]i-1else:closest[i]i1# Step2: 预处理左右相邻移动最小代价R[0]*(n-1)foriinrange(n-1):ifclosest[i]i1:R[i]1else:R[i]nums[i1]-nums[i]L[0]*nforiinrange(1,n):ifclosest[i]i-1:L[i]1else:L[i]nums[i]-nums[i-1]# Step3: 构建前缀和数组prefR[0]*nforiinrange(n-1):prefR[i1]prefR[i]R[i]prefL[0]*nforiinrange(1,n):prefL[i]prefL[i-1]L[i]# Step4: O(1)应答所有查询res[]forl,rinqueries:iflr:res.append(0)eliflr:res.append(prefR[r]-prefR[l])else:res.append(prefL[l]-prefL[r])returnres6. 复杂度分析执行步骤时间复杂度空间复杂度计算 closest 数组O(n)O(n)构建左右代价数组O(n)O(n)构建前缀和数组O(n)O(n)处理所有查询O(q)O(1)整体复杂度O(n q)O(n)该算法为本题最优时间复杂度可完全通过 1e5 极限数据。7. 单调性正确性证明定理任意起点到终点的最小代价路径一定是下标单调路径无折返。证明过程数组严格递增数值差满足三角不等式∣ a − c ∣ ≤ ∣ a − b ∣ ∣ b − c ∣ |a-c| \le |a-b| |b-c|∣a−c∣≤∣a−b∣∣b−c∣。假设存在一条最优路径存在折返先右后左 / 先左后右折返操作会额外累加两段数值差值而捷径的固定代价1仅能节省单次差值开销无法抵消折返带来的额外数值代价。因此任意含折返的路径均可通过去除折返、改为单调直走得到一条代价更小或相等的路径。综上最优路径一定单调无折返贪心策略成立。QED8. 测试与验证编写测试用例验证官方样例与边界数据if__name____main__:solSolution()# 官方样例1nums1[-5,-2,3]q1[[0,2],[2,0],[1,2]]print(sol.minCost(nums1,q1))# 输出 [6,2,5]# 官方样例2nums2[0,2,3,9]q2[[3,0],[1,2],[2,0]]print(sol.minCost(nums2,q2))# 输出 [4,1,3]# 边界测试相同起点终点print(sol.minCost([1,3,5],[[1,1],[0,0]]))# [0,0]所有测试用例完全匹配标准答案算法逻辑无误。9. 总结与扩展核心解题思路总结摒弃暴力思维拒绝图论最短路暴力解法挖掘题目隐藏单调性性质。问题转化将复杂的双规则移动转化为相邻节点最小代价遍历。前缀和优化预处理区间代价将多次查询复杂度降为 O(1)。算法拓展若closest规则修改为「差值最小任意下标」仍可沿用单调性前缀和框架仅需修改预处理逻辑。若新增多种移动代价规则可通过「预处理所有相邻最小代价前缀和」的通用思路求解。CSDN原创声明本文为博主原创技术分享详解LeetCode中等偏上贪心前缀和算法题包含多解法对比、数学证明、完整可运行代码转载请注明出处。