单调队列

今天leetcode的每日一题是和至少为 K 的最短子数组,这道题需要使用前缀和加单调队列。

我当时第一反应是使用滑动窗口算法，但是这道题这样的写法是有问题，我们先看一下我一开始的做法，以及这种做法为什么不行

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function(nums, k) {
    let minLength = nums.length + 1;
    let sum = 0;

    let left = right = 0;

    while(right < nums.length) {
        sum += nums[right];
        right++;

        while(sum >= k) {
            minLength = Math.min(minLength, right - left);
            sum -= nums[left++];
        }
    }

    return minLength === (nums.length + 1) ? -1 : minLength;
};

当输入为[84,-37,32,40,95] 167时，正确答案是3，而滑动窗口做饭的结果是5，因为当right为5的时候，left滑动到1的位置，也就是-37的时候，内部循环就跳出了，但是其实left到2的时候也是符合大于等于167这个条件的

既然我们的滑动窗口做法的问题出在，left收缩的时候可能会在没有收缩到最短的情况下就中断了，那么我们换个思路，在遍历每个right的时候，让left从right处向左扩张，只要遇到第一个符合条件的就是在right确定的时候，符合条件的最短的数组，同时为了节省计算，我们采用前缀和的方式，代码如下：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function(nums, k) {
    let preSum = new Array(nums.length + 1).fill(0);
    for(let i = 1; i < preSum.length; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    let minLength = nums.length + 1;
    let right = 1;
    while(right < preSum.length) {
        let left = right - 1;
        while(left >= 0) {
            if (preSum[right] - preSum[left] >= k) {
                minLength = Math.min(minLength, right - left);
                break;
            }
            left--;
        }
        right++;
    }

    return minLength === preSum.length ? -1 : minLength;
};

不出意外，超时了，那么我们还能怎么优化这个算法呢？

我们可以遍历preSum，用某个合适的数据结构维护遍历过的presum[i],并及时移除无用的presum[i]

• 遍历到preSum[i]时，如果发现preSum[i] - preSum[j] >= k，那么i右侧的的数字无论是什么，都不可能以j为左端点得到一个更短的复合题意的数组，所以将j弹出数据结构
• 如果preSum[i] <= preSum[j],那么如果在i右侧存在某个数x = preSum[m], 满足 x - preSum[j] >= k, 则必然有 x - preSum[i] >= k, 所以将j弹出数据结构

由于优化二保证了数据结构中的 会形成一个递增的序列，因此优化一移除的是序列最左侧的若干元素，优化二移除的是序列最右侧的若干元素。我们需要一个数据结构，它支持移除最左端的元素和最右端的元素，以及在最右端添加元素，故选用双端队列。同时该队列保持递增，所以是个单调队列。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function(nums, k) {
    let preSum = new Array(nums.length + 1).fill(0);
    for(let i = 1; i < preSum.length; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    const queue = [];

    let result = preSum.length;

    for(let i = 0; i < preSum.length; i++) {
        const cur = preSum[i];
        while(queue.length > 0 && cur - preSum[queue[0]] >= k) {
            result = Math.min(result, i - queue[0]);
            queue.shift();
        }
        while(queue.length > 0 && cur <= preSum[queue[queue.length - 1]]) {
            queue.pop();
        }
        queue.push(i);
    }

    return result === preSum.length ? -1 : result;
};