2022-04-17：给定一个数组arr，其中的值有可能正、负、0，给定一个正数k。

福大大架构师每日一题

发布于 2022-06-04 10:33:02

3590

发布于 2022-06-04 10:33:02

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

2022-04-17：给定一个数组arr，其中的值有可能正、负、0，

给定一个正数k。

返回累加和>=k的所有子数组中，最短的子数组长度。

来自字节跳动。力扣862。

答案2022-04-17：

看到子数组，联想到结尾怎么样，开头怎么样。

预处理前缀和，单调栈。

达标的前缀和，哪一个离k最近？

单调栈+二分。复杂度是O(N*logN)。

双端队列。

时间复杂度：O(N)。

代码用rust编写。代码如下：

fn main() {
    let arr: Vec<isize> = vec![2, -1, 2];
    let K: isize = 3;
    let ret = shortest_subarray2(arr, K);
    println!("{}", ret);
}

const MAXVALUE: isize = 9223372036854775807;

fn shortest_subarray2(arr: Vec<isize>, K: isize) -> isize {
    let N = arr.len();
    let mut sum: Vec<isize> = vec![];
    for i in 0..N + 1 {
        sum.push(0);
    }
    for i in 0..N {
        sum[i + 1] = sum[i] + arr[i];
    }
    let mut ans: isize = MAXVALUE;
    let mut dq: Vec<isize> = vec![];
    for i in 0..N + 1 {
        dq.push(0);
    }
    let mut l: isize = 0;
    let mut r: isize = 0;
    for i in 0..N + 1 {
        // 头部开始，符合条件的，从头部弹出！
        while l != r && sum[i] - sum[dq[l as usize] as usize] >= K {
            ans = get_min(ans, i as isize - dq[l as usize]);
            l += 1;
        }
        // 尾部开始，前缀和比当前的前缀和大于等于的，从尾部弹出！
        while l != r && sum[dq[(r - 1) as usize] as usize] >= sum[i as usize] {
            r -= 1;
        }
        dq[r as usize] = i as isize;
        r += 1;
    }
    if ans != MAXVALUE {
        ans
    } else {
        -1
    }
}

fn get_min(a: isize, b: isize) -> isize {
    if a < b {
        a
    } else {
        b
    }
}

执行结果如下：