59 - I. 滑动窗口的最大值.md

题目链接：

「剑指 Offer 59 - I. 滑动窗口的最大值」

思路：

暴力

每次滑动窗口，重新计算窗口中元素的最大值

const maxSlidingWindow = (nums, k) => {
    const res = [];
    const len = nums.length;
    if (!len) return res;
    for (let i = 0; i <= len - k; i++) {
        const temp = [];
        for (let j = i; j < i + k; j++) {
            temp.push(nums[j]);
        }
        res.push(Math.max(...temp));
    }
    return res;
};

单调队列

• 创建队列q，存放的是nums的下标i
• 窗口初始化时，将最初的k个元素的下标入队，并要保证对应的值是依次递减的，若前一个值小于后一个值，则将前一个值下标弹出
• 这样就可以保证，q的队头元素对应的值，肯定是初始窗口中最大的
• 窗口开始滑动，做之前相同的操作。还要将窗口外的值下标弹出队列
• 每次滑动，取出队头下标对应的值即可

const maxSlidingWindow = (nums, k) => {
    const len = nums.length;
    if (!len) return [];
    // q存放的是nums的下标i
    const q = [];
    for (let i = 0; i < k; i++) {
        // 循环比较当前元素和q队尾对应的元素大小，若当前元素大，将队尾元素出队
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
    }
    // 这时候q的队头元素对应的值，肯定是初始窗口中最大的
    const res = [nums[q[0]]];
    for (let i = k; i < len; i++) {
        // 窗口开始滑动，做之前相同的操作
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
        // 窗口滑动，将不应该在窗口中的元素弹出
        while (q[0] <= i - k) q.shift();
        // 这时候q的队头元素对应的值，肯定是当前窗口中最大的
        res.push(nums[q[0]]);
    }
    return res;
};