2026-08-14在下标间移动的最小代价。用go语言给定一个严格递增的整数数组 nums。对于每个下标 x定义 closest(x) 为其相邻下标中的一个如果 x 左右两边都有相邻下标就比较 nums[x] 与左右相邻元素的差值选择差值更小的那个相邻下标如果两个差值相同则选择下标较小的 x-1如果只有一侧有相邻下标就选择该相邻下标。移动方式有两种可以从当前下标 x 直接跳到任意下标 y代价为两个元素差值的绝对值也可以移动到 closest(x)代价为 1。现在给出一组查询 queries每个查询包含两个下标 li 和 ri要求计算从 li 移动到 ri 的最小总代价。返回一个数组按顺序给出每个查询的最小代价。2 nums.length 100000。-1000000000 nums[i] 1000000000。nums 严格递增。1 queries.length 100000。queries[i] [li, ri]。0 li, ri nums.length。输入 nums [-5,-2,3], queries [[0,2],[2,0],[1,2]]。输出 [6,2,5]。解释​​​​​​最近的下标分别是 [1, 0, 1]。对于 [0, 2]路径 0 → 1 → 2 包含一次从下标 0 到 1 的最近移动代价为 1以及一次从下标 1 到 2 的移动代价为 |-2 - 3| 5总代价为 1 5 6。对于 [2, 0]路径 2 → 1 → 0 包含两次最近移动分别从下标 2 到 1 和从下标 1 到 0每次代价为 1总代价为 2。对于 [1, 2]从下标 1 直接移动到下标 2 的代价为 |-2 - 3| 5这是最优的。因此ans [6, 2, 5]。题目来自力扣3919。计算过程详细步骤第一步初始化两个累计代价数组sumL[i]表示从下标i一直向左移动到下标 0 的最小总代价。sumR[i]表示从下标 0 一直向右移动到下标i的最小总代价。长度均为 n初始sumL[0] 0sumR[0] 0。第二步计算从左到右的累计代价sumR我们依次处理 i 从 1 到 n-1目标是计算从 0 移动到 i 的最小代价。对于每一步i-1 - i首先考虑使用“最近移动”方式如果closest(i-1) i那么代价为 1否则只能使用直接跳跃代价为nums[i] - nums[i-1]。那么判断closest(i-1)是否等于 i 的条件是什么对于下标i-1它的右边邻居是 i左边邻居是i-2如果存在。如果左边没有邻居即 i-1 0那它只能往右走此时closest(0) 1代价就是 1。如果左边有邻居比较nums[i-1] - nums[i-2]到左边的距离和nums[i] - nums[i-1]到右边的距离。如果左边距离 ≤ 右边距离那么根据规则选择左边这时closest(i-1) ! i只能用直接跳跃如果左边距离 右边距离则closest(i-1) i代价为 1。在代码中这个条件写作if i 1 nums[i-1]-nums[i-2] nums[i]-nums[i-1] { cost nums[i] - nums[i-1] // 只能用方式一 } else { cost 1 // 用方式二 }注意这里边界 i1 时左边没有邻居直接 cost1。然后sumR[i] sumR[i-1] cost。这样sumR[i]就记录了从 0 到 i 的最小代价。第三步计算从右到左的累计代价sumL对称地我们计算从 i 向左移动到 0 的代价。对于每一步i - i-1判断closest(i)是否等于i-1。如果i的右边没有邻居即 i n-1它只能往左走代价为 1否则比较nums[i] - nums[i-1]到左边距离和nums[i1] - nums[i]到右边距离如果右边距离 左边距离则closest(i) i1此时往左走只能用直接跳跃否则右边距离 ≥ 左边距离则closest(i) i-1代价为 1。代码条件if i n-1 nums[i]-nums[i-1] nums[i1]-nums[i] { cost nums[i] - nums[i-1] // 只能用直接跳 } else { cost 1 }然后sumL[i] sumL[i-1] cost。第四步处理查询对于每个查询[l, r]如果l r即从左往右走从 l 到 r 的最小代价 sumR[r] - sumR[l]。这是因为sumR是前缀和性质且路径不会折返直接从 l 一路向右到 r 就是最优。如果l r即从右往左走从 l 到 r 的最小代价 sumL[l] - sumL[r]。同理这是从 l 一路向左到 r 的累计代价。如果l r代价自然是 0但这个情况未显式处理不过相减也会得到 0。对示例的验证简述nums [-5, -2, 3]n 3计算 sumR从左到右i1左边无邻居 → cost1 → sumR[1]1i2比较 nums[1]-nums[0]3nums[2]-nums[1]5左边距离 3 ≤ 5 → closest(1)0 → 往右必须直接跳代价 5 → sumR[2]156计算 sumL从右到左i1右边有邻居 i2比较 3 vs 5左边距离 3 5 → closest(1)0 → 往左走代价 1 → sumL[1]1i2右边无邻居 → cost1 → sumL[2]112查询[0,2]lr → sumR[2]-sumR[0]6-06[2,0]lr → sumL[2]-sumL[0]2-02[1,2]lr → sumR[2]-sumR[1]6-15结果匹配。复杂度分析时间复杂度预处理一次遍历 nO(n)。查询一次遍历 queries每个查询 O(1)。总 O(n q)其中 q 是查询数量。额外空间复杂度使用了两个长度为 n 的数组 sumL 和 sumRO(n)。答案数组 O(q) 是输出必需的不算额外的话额外空间是 O(n)。若把答案数组也算入则为 O(n q)但按常规额外空间只算辅助数组即 O(n)。最终答案时间复杂度O(n q)额外空间复杂度O(n)Go完整代码如下packagemainimport(fmt)funcminCost(nums[]int,queries[][]int)[]int{n:len(nums)sumL:make([]int,n)// sumL[i] 等于从 i 移动到 0 的代价和sumR:make([]int,n)// sumR[i] 等于从 0 移动到 i 的代价和fori:1;in;i{// 往左走 i - i-1cost:1ifin-1nums[i]-nums[i-1]nums[i1]-nums[i]{// closest(i) i1costnums[i]-nums[i-1]// 只能用方式一往左走}sumL[i]sumL[i-1]cost// 往右走 i-1 - icost1ifi1nums[i-1]-nums[i-2]nums[i]-nums[i-1]{// closest(i-1) i-2costnums[i]-nums[i-1]// 只能用方式一往右走}sumR[i]sumR[i-1]cost}ans:make([]int,len(queries))fori,q:rangequeries{l,r:q[0],q[1]iflr{// cost(0 - r) - cost(0 - l) cost(l - r)ans[i]sumR[r]-sumR[l]}else{// cost(l - 0) - cost(r - 0) cost(l - r)ans[i]sumL[l]-sumL[r]}}returnans}funcmain(){nums:[]int{-5,-2,3}queries:[][]int{{0,2},{2,0},{1,2}}result:minCost(nums,queries)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefminCost(nums:List[int],queries:List[List[int]])-List[int]:nlen(nums)sumL[0]*n# sumL[i] 等于从 i 移动到 0 的代价和sumR[0]*n# sumR[i] 等于从 0 移动到 i 的代价和foriinrange(1,n):# 往左走 i - i-1cost1ifin-1andnums[i]-nums[i-1]nums[i1]-nums[i]:# closest(i) i 1不能通过代价 1 左移只能直接跳costnums[i]-nums[i-1]sumL[i]sumL[i-1]cost# 往右走 i-1 - icost1ifi1andnums[i-1]-nums[i-2]nums[i]-nums[i-1]:# closest(i - 1) i - 2不能通过代价 1 右移只能直接跳costnums[i]-nums[i-1]sumR[i]sumR[i-1]cost ans[]forl,rinqueries:iflr:ans.append(sumR[r]-sumR[l])else:ans.append(sumL[l]-sumL[r])returnansif__name____main__:nums[-5,-2,3]queries[[0,2],[2,0],[1,2]]resultminCost(nums,queries)print(result)C完整代码如下#includevector#includeiostreamusingnamespacestd;vectorintminCost(vectorintnums,vectorvectorintqueries){intnnums.size();vectorintsumL(n,0);// sumL[i] 等于从 i 移动到 0 的代价和vectorintsumR(n,0);// sumR[i] 等于从 0 移动到 i 的代价和for(inti1;in;i){// 往左走 i - i-1intcost1;if(in-1nums[i]-nums[i-1]nums[i1]-nums[i]){// closest(i) i 1不能通过代价 1 左移只能直接跳costnums[i]-nums[i-1];}sumL[i]sumL[i-1]cost;// 往右走 i-1 - icost1;if(i1nums[i-1]-nums[i-2]nums[i]-nums[i-1]){// closest(i - 1) i - 2不能通过代价 1 右移只能直接跳costnums[i]-nums[i-1];}sumR[i]sumR[i-1]cost;}vectorintans;ans.reserve(queries.size());for(constautoq:queries){intlq[0],rq[1];if(lr){ans.push_back(sumR[r]-sumR[l]);}else{ans.push_back(sumL[l]-sumL[r]);}}returnans;}intmain(){vectorintnums{-5,-2,3};vectorvectorintqueries{{0,2},{2,0},{1,2}};vectorintresultminCost(nums,queries);for(size_t i0;iresult.size();i){if(i0)cout, ;coutresult[i];}coutendl;return0;}