forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
JumpGame6.java
28 lines (24 loc) · 930 Bytes
/
JumpGame6.java
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
/*https://leetcode.com/problems/jump-game-vi/*/
class Solution {
public int maxResult(int[] nums, int k) {
// edge cases
if(nums == null || nums.length == 0){
return 0;
}
// initialization
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[0] - a[0]));
// score to index mapping
maxHeap.add(new int[] {nums[0], 0});
int score = nums[0];
// iterate over the elements
for(int index = 1;index < nums.length;index++){
// remove all the maximum while are out of the scope
while(maxHeap.size() > 1 && maxHeap.peek()[1] < index - k){
maxHeap.poll();
}
// add the maximum current score with the index value
maxHeap.add(new int[] {(score = nums[index] + maxHeap.peek()[0]), index});
}
return score;
}
}