Skip to content

2297. Jump Game VIII

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  long long minCost(vector<int>& nums, vector<int>& costs) {
    const int n = nums.size();
    // dp[i] := the minimum cost to jump to i
    vector<long> dp(n, LONG_MAX);
    stack<int> maxStack;
    stack<int> minStack;

    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
      while (!maxStack.empty() && nums[i] >= nums[maxStack.top()])
        dp[i] = min(dp[i], dp[maxStack.top()] + costs[i]), maxStack.pop();
      while (!minStack.empty() && nums[i] < nums[minStack.top()])
        dp[i] = min(dp[i], dp[minStack.top()] + costs[i]), minStack.pop();
      maxStack.push(i);
      minStack.push(i);
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public long minCost(int[] nums, int[] costs) {
    final int n = nums.length;
    // dp[i] := the minimum cost to jump to i
    long[] dp = new long[n];
    Deque<Integer> maxStack = new ArrayDeque<>();
    Deque<Integer> minStack = new ArrayDeque<>();

    Arrays.fill(dp, Long.MAX_VALUE);
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
      while (!maxStack.isEmpty() && nums[i] >= nums[maxStack.peek()])
        dp[i] = Math.min(dp[i], dp[maxStack.pop()] + costs[i]);
      while (!minStack.isEmpty() && nums[i] < nums[minStack.peek()])
        dp[i] = Math.min(dp[i], dp[minStack.pop()] + costs[i]);
      maxStack.push(i);
      minStack.push(i);
    }

    return dp[n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def minCost(self, nums: list[int], costs: list[int]) -> int:
    # dp[i] := the minimum cost to jump to i
    dp = [math.inf] * len(nums)
    maxStack = []
    minStack = []

    dp[0] = 0

    for i, num in enumerate(nums):
      while maxStack and num >= nums[maxStack[-1]]:
        dp[i] = min(dp[i], dp[maxStack.pop()] + costs[i])
      while minStack and num < nums[minStack[-1]]:
        dp[i] = min(dp[i], dp[minStack.pop()] + costs[i])
      maxStack.append(i)
      minStack.append(i)

    return dp[-1]