 多解法超详解析）)
【LeetCode 】在下标间移动的最小代价（贪心+前缀和 O(n+q) 多解法超详解析）
目录
问题描述
示例分析
思路过程
解法一：暴力建图 + 最短路（不可行）
解法二：观察单调性与贪心策略
解法三：前缀和优化（最终最优解）
算法详解
Step1：计算 closest 数组
Step2：定义方向代价
Step3：前缀和预处理
Step4：O(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 \<= nums\.length \<= 10^5\-10^9 \<= nums\[i\] \<= 10^9，nums严格递增1 \<= queries\.length \<= 10^50 \<= li, ri \< nums\.length
2. 示例分析
示例 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 \< r：只向右移动起点
l \> r：只向左移动
贪心策略
相邻两点移动时，永远选择最小代价：
若当前节点捷径指向前进方向，代价为1
否则使用瞬移代价（数值差值）
3.3 解法三：前缀和优化（最终最优解）
基于贪心单调性，预处理左右方向相邻最小代价，再通过前缀和数组预处理区间代价，最终实现O(1) 单次查询，整体复杂度O ( n + q ) O(n+q)O(n+q)，完美适配 1e5 极限数据。
4. 算法详解
4.1 Step1：计算 closest 数组
根据题目规则，遍历每个下标求解最近相邻下标：
首位下标
i=0：无左邻居，closest\[0\] = 1末位下标
i=n\-1：无右邻居，closest\[n\-1\] = n\-2中间下标：对比左右差值，左差值≤右差值选左，否则选右（差值相等选小下标）
n=len(nums)closest=[0]*n closest[0]=1closest[n-1]=n-2foriinrange(1,n-1):left_diff=nums[i]-nums[i-1]right_diff=nums[i+1]-nums[i]ifleft_diff<=right_diff:closest[i]=i-1else:closest[i]=i+14.2 Step2：定义方向代价
定义两个代价数组，存储相邻两点的最小移动代价：
R\[i\]：从i向右走到i\+1的最小代价L\[i\]：从i向左走到i\-1的最小代价
代价规则：捷径指向目标下标则代价为1，否则为数值差值。
# 向右代价 R[i]: i -> i+1R=[0]*(n-1)foriinrange(n-1):ifclosest[i]==i+1:R[i]=1else:R[i]=nums[i+1]-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[i+1]=prefR[i]+R[i]prefL=[0]*nforiinrange(1,n):prefL[i]=prefL[i-1]+L[i]4.4 Step4：O(1) 回答每个查询
根据起点终点大小关系，直接通过前缀和差值计算答案：
l \< r：右行，代价prefR\[r\] \- prefR\[l\]l \> r：左行，代价prefL\[l\] \- prefL\[r\]l == r：无需移动，代价 0
5. 完整代码实现
classSolution:defminCost(self,nums:list[int],queries:list[list[int]])->list[int]:# ©leetcoden=len(nums)ifn<=1:return[0]*len(queries)# Step1: 预处理closest数组closest=[0]*n closest[0]=1closest[-1]=n-2foriinrange(1,n-1):left_diff=nums[i]-nums[i-1]right_diff=nums[i+1]-nums[i]ifleft_diff<=right_diff:closest[i]=i-1else:closest[i]=i+1# Step2: 预处理左右相邻移动最小代价R=[0]*(n-1)foriinrange(n-1):ifclosest[i]==i+1:R[i]=1else:R[i]=nums[i+1]-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[i+1]=prefR[i]+R[i]prefL=[0]*nforiinrange(1,n):prefL[i]=prefL[i-1]+L[i]# Step4: O(1)应答所有查询res=[]forl,rinqueries:ifl==r:res.append(0)elifl<r: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，仅能节省单次差值开销，无法抵消折返带来的额外数值代价。
因此，任意含折返的路径，均可通过去除折返、改为单调直走，得到一条代价更小或相等的路径。
综上：最优路径一定单调无折返，贪心策略成立。QED
8. 测试与验证
编写测试用例，验证官方样例与边界数据：
if__name__=="__main__":sol=Solution()# 官方样例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中等偏上贪心+前缀和算法题，包含多解法对比、数学证明、完整可运行代码，转载请注明出处。
