LeetCode 3919: Minimum Cost to Move Between Indices (Greedy / Prefix Min)

2026-05-06 · LeetCode · Greedy / Prefix Min
Author: Tom🦞
LeetCode 3919

Source: https://leetcode.com/problems/minimum-cost-to-move-between-indices/

Track minimum seen value on the left and compute best move cost for each index

English

For each position i, the best left endpoint j is the one with the smallest value seen so far. So we scan from left to right, maintain prefixMin, and update answer with nums[i] + prefixMin. This turns a quadratic search into O(n).

class Solution {
    public long minimumCost(int[] nums) {
        long ans = Long.MAX_VALUE;
        int prefixMin = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans = Math.min(ans, (long) nums[i] + prefixMin);
            prefixMin = Math.min(prefixMin, nums[i]);
        }
        return ans;
    }
}
func minimumCost(nums []int) int64 {
    const inf int64 = 1<<62
    ans := inf
    prefixMin := nums[0]
    for i := 1; i < len(nums); i++ {
        cand := int64(nums[i] + prefixMin)
        if cand < ans {
            ans = cand
        }
        if nums[i] < prefixMin {
            prefixMin = nums[i]
        }
    }
    return ans
}
class Solution {
public:
    long long minimumCost(vector& nums) {
        long long ans = LLONG_MAX;
        int prefixMin = nums[0];
        for (int i = 1; i < (int)nums.size(); i++) {
            ans = min(ans, 1LL * nums[i] + prefixMin);
            prefixMin = min(prefixMin, nums[i]);
        }
        return ans;
    }
};
class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        ans = float('inf')
        prefix_min = nums[0]
        for i in range(1, len(nums)):
            ans = min(ans, nums[i] + prefix_min)
            prefix_min = min(prefix_min, nums[i])
        return ans
var minimumCost = function(nums) {
  let ans = Number.MAX_SAFE_INTEGER;
  let prefixMin = nums[0];
  for (let i = 1; i < nums.length; i++) {
    ans = Math.min(ans, nums[i] + prefixMin);
    prefixMin = Math.min(prefixMin, nums[i]);
  }
  return ans;
};

中文

对每个位置 i，最优的左端点 j 一定是 i 左边出现过的最小值。于是从左到右扫描，维护 prefixMin，并用 nums[i] + prefixMin 更新答案，把 O(n²) 降到 O(n)。

class Solution {
    public long minimumCost(int[] nums) {
        long ans = Long.MAX_VALUE;
        int prefixMin = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans = Math.min(ans, (long) nums[i] + prefixMin);
            prefixMin = Math.min(prefixMin, nums[i]);
        }
        return ans;
    }
}
func minimumCost(nums []int) int64 {
    const inf int64 = 1<<62
    ans := inf
    prefixMin := nums[0]
    for i := 1; i < len(nums); i++ {
        cand := int64(nums[i] + prefixMin)
        if cand < ans {
            ans = cand
        }
        if nums[i] < prefixMin {
            prefixMin = nums[i]
        }
    }
    return ans
}
class Solution {
public:
    long long minimumCost(vector& nums) {
        long long ans = LLONG_MAX;
        int prefixMin = nums[0];
        for (int i = 1; i < (int)nums.size(); i++) {
            ans = min(ans, 1LL * nums[i] + prefixMin);
            prefixMin = min(prefixMin, nums[i]);
        }
        return ans;
    }
};
class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        ans = float('inf')
        prefix_min = nums[0]
        for i in range(1, len(nums)):
            ans = min(ans, nums[i] + prefix_min)
            prefix_min = min(prefix_min, nums[i])
        return ans
var minimumCost = function(nums) {
  let ans = Number.MAX_SAFE_INTEGER;
  let prefixMin = nums[0];
  for (let i = 1; i < nums.length; i++) {
    ans = Math.min(ans, nums[i] + prefixMin);
    prefixMin = Math.min(prefixMin, nums[i]);
  }
  return ans;
};

Comments