Question

2297. Jump Game VIII

中文文档

Description

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.

 

Example 1:

Input: nums = [3,2,4,4,1], costs = [3,7,6,4,2]
Output: 8
Explanation: You start at index 0.
- Jump to index 2 with a cost of costs[2] = 6.
- Jump to index 4 with a cost of costs[4] = 2.
The total cost is 8. It can be proven that 8 is the minimum cost needed.
Two other possible paths are from index 0 -> 1 -> 4 and index 0 -> 2 -> 3 -> 4.
These have a total cost of 9 and 12, respectively.

Example 2:

Input: nums = [0,1,2], costs = [1,1,1]
Output: 2
Explanation: Start at index 0.
- Jump to index 1 with a cost of costs[1] = 1.
- Jump to index 2 with a cost of costs[2] = 1.
The total cost is 2. Note that you cannot jump directly from index 0 to index 2 because nums[0] <= nums[1].

 

Constraints:

• n == nums.length == costs.length
• 1 <= n <= 105
• 0 <= nums[i], costs[i] <= 105

Solutions

Solution 1

class Solution:
  def minCost(self, nums: List[int], costs: List[int]) -> int:
    n = len(nums)
    g = defaultdict(list)
    stk = []
    for i in range(n - 1, -1, -1):
      while stk and nums[stk[-1]] < nums[i]:
        stk.pop()
      if stk:
        g[i].append(stk[-1])
      stk.append(i)

    stk = []
    for i in range(n - 1, -1, -1):
      while stk and nums[stk[-1]] >= nums[i]:
        stk.pop()
      if stk:
        g[i].append(stk[-1])
      stk.append(i)

    f = [inf] * n
    f[0] = 0
    for i in range(n):
      for j in g[i]:
        f[j] = min(f[j], f[i] + costs[j])
    return f[n - 1]

class Solution {
  public long minCost(int[] nums, int[] costs) {
    int n = nums.length;
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && nums[stk.peek()] < nums[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        g[i].add(stk.peek());
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        g[i].add(stk.peek());
      }
      stk.push(i);
    }
    long[] f = new long[n];
    Arrays.fill(f, 1L << 60);
    f[0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j : g[i]) {
        f[j] = Math.min(f[j], f[i] + costs[j]);
      }
    }
    return f[n - 1];
  }
}

class Solution {
public:
  long long minCost(vector<int>& nums, vector<int>& costs) {
    int n = nums.size();
    vector<int> g[n];
    stack<int> stk;
    for (int i = n - 1; ~i; --i) {
      while (!stk.empty() && nums[stk.top()] < nums[i]) {
        stk.pop();
      }
      if (!stk.empty()) {
        g[i].push_back(stk.top());
      }
      stk.push(i);
    }
    stk = stack<int>();
    for (int i = n - 1; ~i; --i) {
      while (!stk.empty() && nums[stk.top()] >= nums[i]) {
        stk.pop();
      }
      if (!stk.empty()) {
        g[i].push_back(stk.top());
      }
      stk.push(i);
    }
    vector<long long> f(n, 1e18);
    f[0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j : g[i]) {
        f[j] = min(f[j], f[i] + costs[j]);
      }
    }
    return f[n - 1];
  }
};

func minCost(nums []int, costs []int) int64 {
  n := len(nums)
  g := make([][]int, n)
  stk := []int{}
  for i := n - 1; i >= 0; i-- {
    for len(stk) > 0 && nums[stk[len(stk)-1]] < nums[i] {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      g[i] = append(g[i], stk[len(stk)-1])
    }
    stk = append(stk, i)
  }
  stk = []int{}
  for i := n - 1; i >= 0; i-- {
    for len(stk) > 0 && nums[stk[len(stk)-1]] >= nums[i] {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      g[i] = append(g[i], stk[len(stk)-1])
    }
    stk = append(stk, i)
  }
  f := make([]int64, n)
  for i := 1; i < n; i++ {
    f[i] = math.MaxInt64
  }
  for i := 0; i < n; i++ {
    for _, j := range g[i] {
      f[j] = min(f[j], f[i]+int64(costs[j]))
    }
  }
  return f[n-1]
}

function minCost(nums: number[], costs: number[]): number {
  const n = nums.length;
  const g: number[][] = Array.from({ length: n }, () => []);
  const stk: number[] = [];
  for (let i = n - 1; i >= 0; --i) {
    while (stk.length && nums[stk[stk.length - 1]] < nums[i]) {
      stk.pop();
    }
    if (stk.length) {
      g[i].push(stk[stk.length - 1]);
    }
    stk.push(i);
  }
  stk.length = 0;
  for (let i = n - 1; i >= 0; --i) {
    while (stk.length && nums[stk[stk.length - 1]] >= nums[i]) {
      stk.pop();
    }
    if (stk.length) {
      g[i].push(stk[stk.length - 1]);
    }
    stk.push(i);
  }
  const f: number[] = Array.from({ length: n }, () => Infinity);
  f[0] = 0;
  for (let i = 0; i < n; ++i) {
    for (const j of g[i]) {
      f[j] = Math.min(f[j], f[i] + costs[j]);
    }
  }
  return f[n - 1];
}