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, ornums[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.length1 <= n <= 1050 <= nums[i], costs[i] <= 105
Solutions
Solution 1: Monotonic Stack + Dynamic Programming
According to the problem description, we need to find the next position j where nums[j] is greater than or equal to nums[i], and the next position j where nums[j] is less than nums[i]. We can use a monotonic stack to find these two positions in O(n) time, and then construct an adjacency list g, where g[i] represents the indices that index i can jump to.
Then we use dynamic programming to find the minimum cost. Let f[i] represent the minimum cost to jump to index i. Initially, f[0] = 0 and the rest f[i] = ∞. We enumerate the indices i from small to large. For each i, we enumerate each index j in g[i] and perform the state transition f[j] = min(f[j], f[i] + costs[j]). The answer is f[n - 1].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
PythonJavaC++GoTypeScript
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](code-box)
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];
}
}(code-box)
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];
}
};(code-box)
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]
}(code-box)
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];
}(code-box)
