Welcome to Subscribe On Youtube

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

  • 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];
        }
    };
    
  • 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]
    
    
  • 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];
    }
    
    

All Problems

All Solutions