22 lines
691 B
Rust
22 lines
691 B
Rust
|
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
|
||
|
|
}
|
||
|
|
}
|