滑动窗口最大值问题的解决方法及代码实现

滑动窗口最大值问题是一个经典的算法问题，通常用于解决在给定数组中，找到每个固定大小的滑动窗口中的最大值。这个问题可以通过多种方法来解决，包括暴力法、使用双端队列（Deque）等。下面我将详细介绍这些方法，并给出相应的代码实现。

1. 暴力法

暴力法的思路是对于每个窗口，遍历窗口内的所有元素，找到最大值。这种方法的时间复杂度为 O(n*k)，其中 n 是数组的长度，k 是窗口的大小。

function maxSlidingWindow(nums, k) {
    const result = [];
    for (let i = 0; i <= nums.length - k; i++) {
        let max = nums[i];
        for (let j = 1; j < k; j++) {
            if (nums[i + j] > max) {
                max = nums[i + j];
            }
        }
        result.push(max);
    }
    return result;
}

2. 使用双端队列（Deque）

双端队列的方法可以在 O(n) 的时间复杂度内解决这个问题。其核心思想是维护一个双端队列，队列中存储的是数组元素的索引，并且保证队列中的元素是递减的。这样，队列的头部就是当前窗口的最大值。

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // 存储索引

    for (let i = 0; i < nums.length; i++) {
        // 移除不在当前窗口的元素
        if (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift();
        }

        // 移除所有小于当前元素的元素
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }

        // 将当前元素的索引加入队列
        deque.push(i);

        // 如果窗口已经形成，将队列头部的元素加入结果
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

3. 使用堆（Heap）

另一种方法是使用堆（优先队列）来维护窗口中的最大值。这种方法的时间复杂度为 O(n log k)，因为每次插入和删除操作都需要 O(log k) 的时间。

function maxSlidingWindow(nums, k) {
    const result = [];
    const maxHeap = new MaxHeap();

    for (let i = 0; i < nums.length; i++) {
        maxHeap.push(nums[i]);
        if (i >= k - 1) {
            result.push(maxHeap.peek());
            maxHeap.remove(nums[i - k + 1]);
        }
    }

    return result;
}

// 实现一个最大堆
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

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

    remove(val) {
        const index = this.heap.indexOf(val);
        if (index === -1) return;
        this.swap(index, this.heap.length - 1);
        this.heap.pop();
        this.bubbleDown(index);
    }

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) break;
            this.swap(parentIndex, index);
            index = parentIndex;
        }
    }

    bubbleDown(index) {
        while (true) {
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;
            let largestIndex = index;

            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[largestIndex]) {
                largestIndex = leftChildIndex;
            }

            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[largestIndex]) {
                largestIndex = rightChildIndex;
            }

            if (largestIndex === index) break;
            this.swap(index, largestIndex);
            index = largestIndex;
        }
    }

    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
}

总结

• 暴力法：简单直观，但时间复杂度较高，适用于小规模数据。
• 双端队列：时间复杂度为 O(n)，是最优解，适用于大规模数据。
• 堆：时间复杂度为 O(n log k)，适用于需要动态维护最大值的场景。

在实际应用中，双端队列的方法是最常用的解决方案，因为它既高效又易于实现。