2026-08-14：在下标间移动的最小代价。用go语言，给定一个严格递增的整数数组 nums。对于每个下标 x，定义 closest(x) 为其相邻下标中的

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] = 0，sumR[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                     // 用方式二
}

注意这里边界 i=1 时，左边没有邻居，直接 cost=1。

然后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[i+1] - nums[i]（到右边距离）：

• • • 如果右边距离 < 左边距离，则closest(i) = i+1，此时往左走只能用直接跳跃；

  • • 否则（右边距离 ≥ 左边距离），则closest(i) = i-1，代价为 1。

代码条件：

if i < n-1 && nums[i]-nums[i-1] > nums[i+1]-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（从左到右）

• • i=1：左边无邻居 → cost=1 → sumR[1]=1

• • i=2：比较 nums[1]-nums[0]=3，nums[2]-nums[1]=5，左边距离 3 ≤ 5 → closest(1)=0 → 往右必须直接跳，代价 5 → sumR[2]=1+5=6

• • i=1：右边有邻居 i=2，比较 3 vs 5，左边距离 3 < 5 → closest(1)=0 → 往左走代价 1 → sumL[1]=1

• • i=2：右边无邻居 → cost=1 → sumL[2]=1+1=2

查询：

• • [0,2]：l

• • [2,0]：l>r → sumL[2]-sumL[0]=2-0=2

• • [1,2]：l

结果匹配。

复杂度分析

• •时间复杂度：

• • • 预处理：一次遍历 n，O(n)。

  • • 查询：一次遍历 queries，每个查询 O(1)。

  • • 总 O(n + q)，其中 q 是查询数量。

• •额外空间复杂度：

• • • 使用了两个长度为 n 的数组 sumL 和 sumR，O(n)。

  • • 答案数组 O(q) 是输出必需的，不算额外的话，额外空间是 O(n)。

  • • 若把答案数组也算入，则为 O(n + q)，但按常规额外空间只算辅助数组，即 O(n)。

最终答案：

• • 时间复杂度：O(n + q)

• • 额外空间复杂度：O(n)

package main

 import (
    "fmt"
)

 func minCost(nums []int, queries [][]int) []int {
    n := len(nums)
    sumL := make([]int, n) // sumL[i] 等于从 i 移动到 0 的代价和
    sumR := make([]int, n) // sumR[i] 等于从 0 移动到 i 的代价和
    for i := 1; i < n; i++ {
        // 往左走 i -> i-1
        cost := 1
        if i < n-1 && nums[i]-nums[i-1] > nums[i+1]-nums[i] { // closest(i) = i+1
            cost = nums[i] - nums[i-1] // 只能用方式一往左走
        }
        sumL[i] = sumL[i-1] + cost

         // 往右走 i-1 -> i
        cost = 1
        if i > 1 && nums[i-1]-nums[i-2] <= nums[i]-nums[i-1] { // closest(i-1) = i-2
            cost = nums[i] - nums[i-1] // 只能用方式一往右走
        }
        sumR[i] = sumR[i-1] + cost
    }

     ans := make([]int, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]
        if l < r {
            // 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]
        }
    }
    return ans
}

 func main() {
    nums := []int{-5, -2, 3}
    queries := [][]int{{0, 2}, {2, 0}, {1, 2}}
    result := minCost(nums, queries)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def minCost(nums: List[int], queries: List[List[int]]) -> List[int]:
    n = len(nums)
    sumL = [0] * n  # sumL[i] 等于从 i 移动到 0 的代价和
    sumR = [0] * n  # sumR[i] 等于从 0 移动到 i 的代价和

     for i in range(1, n):
        # 往左走 i -> i-1
        cost = 1
        if i < n - 1 and nums[i] - nums[i - 1] > nums[i + 1] - nums[i]:
            # closest(i) = i + 1，不能通过代价 1 左移，只能直接跳
            cost = nums[i] - nums[i - 1]
        sumL[i] = sumL[i - 1] + cost

         # 往右走 i-1 -> i
        cost = 1
        if i > 1 and nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1]:
            # closest(i - 1) = i - 2，不能通过代价 1 右移，只能直接跳
            cost = nums[i] - nums[i - 1]
        sumR[i] = sumR[i - 1] + cost

     ans = []
    for l, r in queries:
        if l < r:
            ans.append(sumR[r] - sumR[l])
        else:
            ans.append(sumL[l] - sumL[r])
    return ans

 if __name__ == "__main__":
    nums = [-5, -2, 3]
    queries = [[0, 2], [2, 0], [1, 2]]
    result = minCost(nums, queries)
    print(result) 

C++完整代码如下：

  

  


 using namespace std;

 vector minCost(vector& nums, vector 
 
 int 
 >>& queries) { 
 
 
      
 int 
  n = nums.size(); 
 
 
     vector< 
 int 
 > sumL(n,  
 0 
 );  
 // sumL[i] 等于从 i 移动到 0 的代价和 
 
 
     vector< 
 int 
 > sumR(n,  
 0 
 );  
 // sumR[i] 等于从 0 移动到 i 的代价和 
 
 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i < n; ++i) { 
 
 
          
 // 往左走 i -> i-1 
 
 
          
 int 
  cost =  
 1 
 ; 
 
 
          
 if 
  (i < n -  
 1 
  && nums[i] - nums[i -  
 1 
 ] > nums[i +  
 1 
 ] - nums[i]) { 
 
 
              
 // closest(i) = i + 1，不能通过代价 1 左移，只能直接跳 
 
 
             cost = nums[i] - nums[i -  
 1 
 ]; 
 
 
         } 
 
 
         sumL[i] = sumL[i -  
 1 
 ] + cost; 
 
 
 
 
          
 // 往右走 i-1 -> i 
 
 
         cost =  
 1 
 ; 
 
 
          
 if 
  (i >  
 1 
  && nums[i -  
 1 
 ] - nums[i -  
 2 
 ] <= nums[i] - nums[i -  
 1 
 ]) { 
 
 
              
 // closest(i - 1) = i - 2，不能通过代价 1 右移，只能直接跳 
 
 
             cost = nums[i] - nums[i -  
 1 
 ]; 
 
 
         } 
 
 
         sumR[i] = sumR[i -  
 1 
 ] + cost; 
 
 
     } 
 
 
 
 
     vector< 
 int 
 > ans; 
 
 
     ans.reserve(queries.size()); 
 
 
      
 for 
  ( 
 const 
  auto& q : queries) { 
 
 
          
 int 
  l = q[ 
 0 
 ], r = q[ 
 1 
 ]; 
 
 
          
 if 
  (l < r) { 
 
 
             ans.push_back(sumR[r] - sumR[l]); 
 
 
         }  
 else 
  { 
 
 
             ans.push_back(sumL[l] - sumL[r]); 
 
 
         } 
 
 
     } 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums = { 
 -5 
 ,  
 -2 
 ,  
 3 
 }; 
 
 
     vector 
 
 int 
 >> queries = {{ 
 0 
 ,  
 2 
 }, { 
 2 
 ,  
 0 
 }, { 
 1 
 ,  
 2 
 }}; 
 
 
     vector< 
 int 
 > result = minCost(nums, queries); 
 
 
      
 for 
  (size_t i =  
 0 
 ; i < result.size(); ++i) { 
 
 
          
 if 
  (i >  
 0 
 ) cout <<  
 ", " 
 ; 
 
 
         cout << result[i]; 
 
 
     } 
 
 
     cout << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。