239. 滑动窗口最大值

Problem: 239. 滑动窗口最大值

方法一： 最大堆

思路

可以创建一个满足 k 个元素的最大堆，同时将元素的下标也保存起来，如果滑动窗口中的元素个数大于等于 k 时，可以直接取最大堆里的最大元素的值，同时需要需要判断，这个最大元素是否还在窗口内，如果不在，则将元素出队，重新构建新的最大堆，求得最大值。

由于 JavaScript 中没有现有的最大堆，可以自己实现一个最大堆。最大堆实现详见：用 JavaScript 实现优先队列和堆。

代码

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const maxHeap = new MaxHeap((a, b) => b?.[0] - a?.[0]);
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        maxHeap.add([nums[i], i]);
        if (i + 1 >= k) {
            let top = maxHeap.peek();
            while (top[1] <= i - k) {
                maxHeap.remove();
                top = maxHeap.peek();
            }
            result.push(top[0])
        }
    }
    return result;
};

class MaxHeap {
    constructor(comparator = (a, b) => a - b) {
        this.array = [];
        this.comparator = (i1, i2) => comparator(this.array[i1], this.array[i2]);
    }

    get size() {
        return this.array.length;
    }

    swap(a, b) {
        [this.array[a], this.array[b]] = [this.array[b], this.array[a]];
    }

    peek() {
        return this.array[0];
    }

    add(value) {
        this.array.push(value);
        this.bubbleUp();
    }

    bubbleUp() {

        let curr = this.size - 1;
        const parent = i => Math.ceil(i / 2) - 1;
        while (curr >= 0 && this.comparator(parent(curr), curr) > 0) {
            this.swap(parent(curr), curr);
            curr = parent(curr);
        }
    }

    remove(index = 0) {
        if (!this.size) return null
        this.swap(index, this.size - 1);
        const value = this.array.pop();
        this.bubbleDown();
        return value;
    }

    bubbleDown(index = 0) {
        let curr = index;
        const left = i => i * 2 + 1;
        const right = i => i * 2 + 2;
        const getTopChild = i => right(i) < this.size && this.comparator(left(i), right(i)) > 0 ? right(i) : left(i);
        while (left(curr) < this.size && this.comparator(curr, getTopChild(curr)) > 0) {
            const next = getTopChild(curr);
            this.swap(next, curr);
            curr = next;
        }
    }
}

复杂度分析

时间复杂度	空间复杂度
O(log n)	O(n)

方法二：单调队列

思路

要求得滑动窗口内 k 个元素的最大值，需要最基本的两个步骤：

• 求 k 个元素的最大值，加入结果 res 中
• 这个最大值必须要在窗口内

因此我们可以使用单调队列。每次使用单调队列来维护 k 个元素的最大值，并且判断最大值是否在窗口内即可。

单调队列 是一种所有元素保持单调递增或者单调递减的队列。拿单调递增队列来说，用队尾的元素和入队的元素比较，如果入队的元素大于等于队尾的元素，则队尾元素出队，一直到队尾的元素小于入队的元素为止，然后再添加该入队的元素。

简单来说，要维护单调递增队列，让最大的元素进入队列并且比它小的都移出即可。山大王来了，小的们要让位。

比如，我们现在有一个数组：[1, 3, 2, 5, 8, 7]，求它的窗口内 k = 3 的最大值过程如下：

注意：这道题里面，我们还需要判断最大值是否还在窗口内，因此单调队列中保存的是值的下标。

代码

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const q = [];
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        while (q && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
        //  如果第一个元素已经不在 window 中了，移除它
        if (q[0] === i - k) {
            q.shift();
        }

        // 如果 window 中有 k 个元素，则将当前最大值加入 res 中
        if (i >= k - 1) {
            res.push(nums[q[0]])
        }
    }
    return res;
};

总结

我们使用了优先队列和单调队列来解这道题，其实无论使用哪种方式，核心思想都是需要维护一个 k 个元素，能否方便取得它的最大值（维护最大堆或者单调递增队列），并且保证这个最大值还在滑动窗口中。

复杂度分析

时间复杂度	空间复杂度
O(n)	O(k)
n 是数组 nums 的长度，每一个下标恰好被放入队列一次，并且最多被弹出队列一次。	不断从队首弹出元素，保证了队列中不会有超过 k + 1 个元素，因此队列使用的空间为 O(k)

参考资料

用栈实现队列

Sliding Window Maximum | Monotonic Stack