给定一个正数数组arr，长度为N，依次代表N个任务的难度，给定一个正数k，
你只能从0任务开始，依次处理到N-1号任务结束，就是一定要从左往右处理任务，
只不过，难度差距绝对值不超过k的任务，可以在一天之内都完成。
返回完成所有任务的最少天数。
动态规划+窗口内最大值最小值更新结构。
代码用rust编写。代码如下：
fn main() {
let arr: Vec<i32> = vec![1, 2, 3, 4, 5, 6, 7];
let ans = min_days2(&arr, 5);
println!("ans = {}", ans);
}
fn min_days2(arr: &Vec<i32>, k: i32) -> i32 {
let n = arr.len() as i32;
let mut dp: Vec<i32> = vec![];
let mut window_max: Vec<i32> = vec![];
let mut window_min: Vec<i32> = vec![];
for _i in 0..n {
dp.push(0);
window_max.push(0);
window_min.push(0);
}
let mut max_l: i32 = 0;
let mut max_r: i32 = 0;
let mut min_l: i32 = 0;
let mut min_r: i32 = 0;
let mut l: i32 = 0;
for i in 0..n {
while max_l < max_r && arr[window_max[(max_r - 1) as usize] as usize] <= arr[i as usize] {
max_r -= 1;
}
window_max[max_r as usize] = i;
max_r += 1;
while min_l < min_r && arr[window_min[(min_r - 1) as usize] as usize] >= arr[i as usize] {
min_r -= 1;
}
window_min[min_r as usize] = i;
min_r += 1;
while arr[window_max[max_l as usize] as usize] - arr[window_min[min_l as usize] as usize]
> k
{
if window_max[max_l as usize] == l {
max_l += 1;
}
if window_min[min_l as usize] == l {
min_l += 1;
}
l += 1;
}
dp[i as usize] = 1 + if l - 1 >= 0 { dp[(l - 1) as usize] } else { 0 };
}
return dp[(n - 1) as usize];
}执行结果如下：
