Jump game viii

Array Dynamic Programming Stack Graph Theory Monotonic Stack Shortest Path

45.6% acceptance

Mar 31, 2026

173

You are given a 0-indexed integer array nums of length n. You are initially standing at index 0. You can jump from index i to index j where i < j if: nums[i] <= nums[j] and nums[k] < nums[i] for all indexes k in the range i < k < j, or nums[i] > nums[j] and nums[k] >= nums[i] for all indexes k in the range i < k < j. You are also given an integer array costs of length n where costs[i] denotes the cost of jumping to index i. Return the minimum cost to jump to the index n - 1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(nums: Vec<i32>, costs: Vec<i32>) -> i64 {
    let n = nums.len();
    let mut dp = vec![i64::MAX; n];
    dp[0] = 0;
    let mut stack_ge: Vec<usize> = vec![];
    let mut stack_lt: Vec<usize> = vec![];
    for j in 0..n {
      while !stack_ge.is_empty() && nums[*stack_ge.last().unwrap()] <= nums[j] {
        let i = stack_ge.pop().unwrap();
        if dp[i] != i64::MAX {
          dp[j] = dp[j].min(dp[i] + costs[j] as i64);
        }
      }
      stack_ge.push(j);
      while !stack_lt.is_empty() && nums[*stack_lt.last().unwrap()] > nums[j] {
        let i = stack_lt.pop().unwrap();
        if dp[i] != i64::MAX {
          dp[j] = dp[j].min(dp[i] + costs[j] as i64);
        }
      }
      stack_lt.push(j);
    }
    dp[n - 1]
  }
}