239. 滑动窗口最大值

[Geekhyt]

原题链接

单调队列

1.维护一个单调递减队列，从大到小，左边是出口，右边是入口
2.每次 pop 时需要判断当前队列是否为空，并且如果当前要弹出的数值等于队列出口元素时，队列移除出口元素
3.每次 push 的元素如果大于入口元素，将队列后端的数值弹出，直到 push 的元素数值小于队列入口元素，保证单调性
4.max 可以获取当前队列的最大值

const maxSlidingWindow = function(nums, k) {
    const n = nums.length
    class slideWindow {
        constructor() {
            this.data = []
        }
        push(val) {
            let data = this.data
            while (data.length > 0 && data[data.length - 1] < val) {
                data.pop()
            }
            data.push(val)
        }
        pop(val) {
            let data = this.data
            if (data.length > 0 && data[0] === val) {
                data.shift()
            }
        }
        max() {
            return this.data[0]
        }
    }
    let res = []
    let windows = new slideWindow()
    for (let i = 0; i < n; i++) {
        if (i < k - 1) {
            windows.push(nums[i])
        } else {
            windows.push(nums[i])
            res.push(windows.max())
            windows.pop(nums[i - k + 1])
        }
    }
    return res
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)