单调队列

栈有单调栈,队列自然也有单调队列,性质也是一样的,保持队列内的元素有序,单调递增或递减。

其实动态求极值首先可以联想到的应该是 「优先队列」,但是,优先队列无法满足**「先进先出」**的时间顺序,所以单调队列应运而生。

js

// 关键点, 保持单调性,其拍平效果与单调栈一致
while (q.length && num (<= | >=) q[q.length - 1]) {
    q.pop()
}
q.push(num)

给你一个数组 window,已知其最值为 A,如果给 window 中添加一个数 B,那么比较一下 A 和 B 就可以立即算出新的最值;但如果要从 window 数组中减少一个数,就不能直接得到最值了,因为如果减少的这个数恰好是 A,就需要遍历 window 中的所有元素重新寻找新的最值。

动态计算极值,直接命中单调队列的使用条件。

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    let res = []
    const monoQueue = []
    for (let i = 0; i < nums.length; ++i) {
        while (monoQueue.length && nums[i] >= nums[monoQueue[monoQueue.length - 1]]) {
            monoQueue.pop()
        }
        /** 一个重点是存储索引,便于判断窗口的大小 */
        monoQueue.push(i)
        if (i - monoQueue[0] + 1 > k) monoQueue.shift()

        // r - l + 1 == k 所以 l = r - k + 1 保证有意义
        if (i - k + 1 >= 0) res.push(nums[monoQueue[0]])
    }
    return res
}

看题目就知道,离不开前缀和。想到单调队列,是有难度的,起码我一开始想不到 😭

js

var shortestSubarray = function (nums, k) {
    const n = nums.length
    const preSumArr = new Array(n + 1).fill(0)
    for (let i = 0; i < n; i++) {
        preSumArr[i + 1] = preSumArr[i] + nums[i]
    }
    let res = n + 1
    const queue = []
    for (let i = 0; i <= n; i++) {
        const curSum = preSumArr[i]
        while (queue.length != 0 && curSum - preSumArr[queue[0]] >= k) {
            res = Math.min(res, i - queue.shift())
        }
        while (queue.length != 0 && preSumArr[queue[queue.length - 1]] >= curSum) {
            queue.pop()
        }
        queue.push(i)
    }
    return res < n + 1 ? res : -1
}

这道题在前缀和的时候遇到过,再来复习一次吧 😁

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubarraySumCircular = function (nums) {
    // 这道题是比较综合的一道题,用到了前缀和,循环数组技巧,滑动窗口和单调队列技巧
    let max = -Infinity
    const monoQueue = [[0, nums[0]]] // 单调队列存储 【index,preSum】的数据结构
    const n = nums.length
    let preSum = nums[0]
    for (let i = 1; i < 2 * n; ++i) {
        preSum += nums[i % n]
        max = Math.max(max, preSum - monoQueue[0][1]) // 子数组和越大,减去的就应该越小
        while (monoQueue.length && preSum <= monoQueue[monoQueue.length - 1][1]) {
            monoQueue.pop()
        }
        monoQueue.push([i, preSum])
        // 根据索引控制 窗口大小
        while (monoQueue.length && i - monoQueue[0][0] + 1 > n) {
            monoQueue.shift()
        }
    }
    return max
}