leet-code/jump-game-vi/sol.rs

22 lines
691 B
Rust
Raw Permalink Normal View History

2022-07-09 22:34:05 +00:00
use std::collections::BinaryHeap;
impl Solution {
pub fn max_result(nums: Vec<i32>, k: i32) -> i32 {
let mut heap = BinaryHeap::new();
let max_step = k as usize;
heap.push((nums[0], 0));
for p in 1..nums.len() {
let mut max_path = heap.peek().unwrap();
while max_path.1 + max_step < p {
heap.pop();
max_path = heap.peek().unwrap();
}
if p == nums.len() - 1 {
return nums[p] + max_path.0;
} else {
heap.push((nums[p] + max_path.0, p));
}
}
nums[0] // Only possible to reach when nums.len() == 1
}
}