Monotone Queue

Posted on Edited on In Waline:

Today’s daily question of leetcode is和至少为 K 的最短子数组This question requires the use of prefixes and monotone queues.

My first reaction at that time was to use the sliding window algorithm, but this question is written in such a way that there is a problem. Let’s take a look at my initial approach and why this approach does not work

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @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;
};

When the input is’ [84, -37,32,40,95] 167 ', the correct answer is 3, and the result of the sliding window cooking is 5, because when right is 5, left slides to the position of 1, which is -37, the internal loop jumps out, but in fact, when left to 2, it also meets the condition of greater than or equal to 167

Since the problem with our sliding window approach is that the left contraction may be interrupted when there is no contraction to the shortest, then we change our thinking and let the left expand from the right to the left when traversing each right., as long as the first one that meets the condition is the shortest array that meets the condition when the right is determined, at the same time, in order to save calculation, we use the prefix sum method. The code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @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;
};

Not surprisingly, it timed out, so how else can we optimize this algorithm?

We can traverse the preSum, maintain the traversed presum [i] with a suitable data structure, and remove the useless presum [i] in time

  • When traversing to preSum [i], if preSum [i] - preSum [j] > = k is found, then no matter what the number on the right side of i is, it is impossible to get a shorter composite question with j as the left endpoint. Array, so pop j out of the data structure
    -If preSum [i] < = preSum [j], then if there is some number x = preSum [m] on the right side of i, such that x - preSum [j] > = k, then there must be x - preSum [i] > = k, so pop j out of the data structure

Since Optimization 2 guarantees that an increasing sequence will be formed in the data structure, Optimization 1 removes several elements on the leftmost side of the sequence, and Optimization 2 removes several elements on the rightmost side of the sequence. We need a data structure that supports removing the leftmost element and the rightmost element, and adding elements at the rightmost end, so we choose a double-ended queue. At the same time, the queue remains incremental, so it is a monotonous queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @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;
};