Stack
Graph
Array
Dynamic Programming
Shortest Path
Monotonic Stack
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
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 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 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 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 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 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 ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 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 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 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 ];
}
GitHub