239. 滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

• 239. 滑动窗口最大值

  • 题目描述

  • 方法 1：暴力法(TLE)

    • 思路

    • 复杂度分析

    • 代码

  • 方法 2：大顶堆(TLE)

    • 思路

    • 复杂度分析

    • 代码

  • 方法 3：平衡二叉搜索树

    • 思路

    • 复杂度分析

    • 代码(TODO)

  • 方法 4：deque

    • 思路

    • 复杂度分析

    • 代码

题目描述

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。



进阶：

你能在线性时间复杂度内解决此题吗？



示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7


提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：暴力法(TLE)

思路

直觉想法，当然是在滑动窗口每次滑动时都遍历窗口找到最大值，果不其然超时了 ╮（╯＿╰）╭

49 / 59 个通过测试用例

复杂度分析

• 时间复杂度：$O((N-k)*k)$，N 是数组长度。

• 空间复杂度：$O(1)$。

代码

JavaScript Code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    const res = [];
    for (let i = 0; i <= nums.length - k; i++) {
        res.push(Math.max(...nums.slice(i, i + k)));
    }
    return res;
};

方法 2：大顶堆(TLE)

思路

要找最大值，自然而然就能想到堆了。

但如果直接每个滑动窗口都建一个堆的话，

• 时间复杂度是 $O(klogk*(N-k))$：

  • 其中建堆的时间是 $O(klogk)$。

  • 一共有 $N-k+1$ 个滑动窗口。

• 空间复杂度是 $O(k)$，堆的大小。

这样时间复杂度还是太高了，会超时(49 / 59 个通过测试用例)。

优化

我们要记住固定长度滑动窗口的特点，就是 每次滑动变动的只有头尾两个元素。

如果我们能在窗口滑动时用新元素替换旧元素，再对堆进行 heapify 操作，这样时间复杂度就变成了：

• 建堆时间复杂度是 $O(klogk)$。

• 滑动窗口滑动时，替换元素的时间是 $O(k+logk)$，

  • 其中找到旧元素的时间是 $O(k)$

  • heapify 的时间是 $O(logk)$

• 一共有 $N-k+1$ 个滑动窗口，所以总的时间复杂度是 $O(klogk + (N-k)(logk + k))$

• 也就是 $O(N*k)$ 吧 (⓿_⓿) 大概可以这样约掉...忽略掉其中较小的数

原以为能 AC 的，大意了，还是 TLE。

JavaScript: 52 / 59 个通过测试用例 Python: 49 / 59 个通过测试用例

复杂度分析

• 时间复杂度：$O(N*k)$。

• 空间复杂度：$O(k)$。

代码

Python Code

from heapq import heapify

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        for i, n in enumerate(nums):
            nums[i] = -n

        l, r = 0, k - 1
        heap = nums[0:r+1]
        heapify(heap)

        res = []
        res.append(-heap[0])

        while r < len(nums) - 1:
            r += 1
            heap[heap.index(nums[l])] = nums[r]
            heapify(heap)
            l += 1
            res.append(-heap[0])
        return res

JavaScript Code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    if (!nums || !nums.length) return [];

    const heap = new MaxHeap(nums.slice(0, k));
    const res = [];
    res.push(heap.peek());

    let l = 0,
        r = k - 1;
    while (r < nums.length - 1) {
        r++;
        heap.replace(nums[l], nums[r]);
        l++;
        res.push(heap.peek());
    }

    return res;
};

// *******************************************

class Heap {
    constructor(list = [], comparator) {
        this.list = list;
        this.comparator = comparator;

        this.init();
    }

    init() {
        const size = this.size();
        for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
            this.heapify(this.list, size, i);
        }
    }

    insert(n) {
        this.list.push(n);
        const size = this.size();
        for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
            this.heapify(this.list, size, i);
        }
    }

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

    pop() {
        const last = this.list.pop();
        if (this.size() === 0) return last;
        const returnItem = this.list[0];
        this.list[0] = last;
        this.heapify(this.list, this.size(), 0);
        return returnItem;
    }

    replace(replaced, target) {
        const index = this.list.findIndex(n => n === replaced);
        if (index > -1) {
            this.list[index] = target;
            const size = this.size();
            for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
                this.heapify(this.list, size, i);
            }
            return true;
        }
        return false;
    }

    size() {
        return this.list.length;
    }
}

class MaxHeap extends Heap {
    constructor(list, comparator) {
        if (typeof comparator != 'function') {
            comparator = function comparator(inserted, compared) {
                return inserted < compared;
            };
        }
        super(list, comparator);
    }

    heapify(arr, size, i) {
        let largest = i;
        const left = Math.floor(i * 2 + 1);
        const right = Math.floor(i * 2 + 2);

        if (left < size && this.comparator(arr[largest], arr[left]))
            largest = left;
        if (right < size && this.comparator(arr[largest], arr[right]))
            largest = right;

        if (largest !== i) {
            [arr[largest], arr[i]] = [arr[i], arr[largest]];
            this.heapify(arr, size, largest);
        }
    }
}

方法 3：平衡二叉搜索树

思路

• 滑动窗口的大小是 k，我们要找出 k 个数字中的最大值。

• 窗口每次滑动时变化的只有头尾两个数字。

基于以上两点，我们可以考虑用一个数据结构来存这 k 个数字，每次窗口滑动时，用 nums[r+1] 替换掉 nums[l]，然后再返回 k 个数字中的最大值。

因此我们需要的是一个可以快速找到 nums[l]，还能快速找到最大值，也就是，能 快速查找值 的数据结构。就是你啦！二叉搜索树！

不过，二叉搜索树有可能会退化成链表，搜索时间变成 $O(N)$，而平衡二叉搜索树，也就是 AVL 树，作为升级版的二叉搜索树，它的搜索时间永远是 $O(logN)$，所以我们可以用 AVL 树。

由于我还没有写过 AVL 树，这里就偷懒不写啦。(。_。) 不知道会不会超时。

复杂度分析

• 时间复杂度：$O((N-k)*logk)$，N 是数组长度，一共有 $N-k+1$ 个滑动窗口，$logk$ 是向 AVL 树插入和查询值的时间。

• 空间复杂度：$O(k)$，AVL 树的大小。

代码(TODO)

JavaScript Code

// TODO

方法 4：deque

思路

直觉解法全都超时了，看来虽然题目说进阶是线性时间，但我看它根本就是要求线性时间！

题目给了提示说可以用 deque。没力气写太多，直接看代码注释吧 ( ╯□╰ )。

复杂度分析

• 时间复杂度：$O(N)$，N 是数组长度，每个数字最多入列出列一次。

• 空间复杂度：$O(k)$，deque 的空间。

代码

JavaScript Code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    const res = [];
    // deque 头部是较大的数字，尾部是较小的数字
    const deque = new Deque();

    let l = 0,
        r = 0;

    // 第一个滑动窗口
    while (r < k) {
        // 让所有比 nums[r] 小的数字都出列
        // 因为 nums[r] 在它们右边，窗口滑动的时候，这些数字肯定比 nums[r] 更早滑出窗口
        // 有 nums[r] 在，最大值轮不到它们，所以它们没用，出列
        while (deque.rear < nums[r]) {
            deque.popRear();
        }
        deque.pushRear(nums[r]);
        r++;
    }
    // 第一个滑动窗口中的最大值
    res.push(deque.front);

    // 滑动窗口右移中
    while (r < nums.length) {
        // 如果左边滑出的数字是最大值，将它从 deque 中出列
        if (nums[l] === deque.front) deque.popFront();
        l++;
        // 同理，所有比 nums[r] 小的数字都出列
        while (deque.rear < nums[r]) {
            deque.popRear();
        }
        deque.pushRear(nums[r]);
        res.push(deque.front);
        r++;
    }

    return res;
};

// ******************************
// PS. 不是 Deque，随便用数组模拟下，实际复杂度要比 deque 高。
class Deque {
    constructor() {
        this.list = [];
    }
    get front() {
        return this.list[0];
    }
    get rear() {
        return this.list[this.list.length - 1];
    }
    popFront() {
        this.list.shift();
    }
    popRear() {
        this.list.pop();
    }
    pushFront(val) {
        this.list.unshift(val);
    }
    pushRear(val) {
        this.list.push(val);
    }
}

单调队列 @feiker

JavaScript Code

var maxSlidingWindow = function (nums, k) {
    const res = [];
    const dequeue = new Dequeue();

    // 前 k 个数据入队
    for (let i = 0; i < k - 1; i++) {
        dequeue.push(nums[i]);
    }

    // 滑动窗口
    for (let i = k - 1; i < nums.length; i++) {
        dequeue.push(nums[i]);
        res.push(dequeue.front);
        dequeue.shift(nums[i - k + 1]);
    }
    return res;
};

class Dequeue {
    constructor() {
        this.list = [];
    }

    get front() {
        return this.list[0];
    }

    get tail() {
        return this.list[this.list.length - 1];
    }

    push(val) {
        const list = this.list;
        // 保证数据从队头到队尾递减
        while (this.tail < val) {
            list.pop();
        }
        list.push(val);
    }

    // 队头出队
    shift(val) {
        // 这里的js实现shift()理论上复杂度应该是O(k), 就不去真实实现一个O(1)出队的队列了，意思到位即可
        if (this.front === val) this.list.shift();
    }
}