2022-05-20：给定一个正数数组arr，长度为N，依次代表N个任务的难度，给定一个正数k，你只能从0任务开始，依次处理到N-1号任务结束

原创

福大大架构师每日一题

发布于 2022-05-20 12:34:16

4270

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-05-20：给定一个正数数组arr，长度为N，依次代表N个任务的难度，给定一个正数k，

你只能从0任务开始，依次处理到N-1号任务结束，就是一定要从左往右处理任务，

只不过，难度差距绝对值不超过k的任务，可以在一天之内都完成。

返回完成所有任务的最少天数。

来自微软。

答案2022-05-20：

动态规划+窗口内最大值最小值更新结构。

代码用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_mx.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];
}