滑动窗口最大值 ​

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

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

 

// 示例 1：

// 输入：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
// 示例 2：

// 输入：nums = [1], k = 1
// 输出：[1]
var maxSlidingWindow = function (nums, k) {
    // 记录返回结果
    const res = []
    // 记录单调递减下标队列
    const q = []
    for (let i = 0;i < nums.length;i++) {
        // 保证单调递减
        while (q.length && nums[q[q.length - 1]] <= nums[i]) {
            q.pop()
        }
        q.push(i)
        // i - q[0] >= k 表示窗口已经移出
        if (i - q[0] >= k) {
            q.shift()
        }
        // i >= k - 1 表示窗口已经形成,记录最大值
        if (i >= k - 1) {
            res.push(nums[q[0]])
        }
    }
    return res
};

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

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

 

// 示例 1：

// 输入：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
// 示例 2：

// 输入：nums = [1], k = 1
// 输出：[1]
var maxSlidingWindow = function (nums, k) {
    // 记录返回结果
    const res = []
    // 记录单调递减下标队列
    const q = []
    for (let i = 0;i < nums.length;i++) {
        // 保证单调递减
        while (q.length && nums[q[q.length - 1]] <= nums[i]) {
            q.pop()
        }
        q.push(i)
        // i - q[0] >= k 表示窗口已经移出
        if (i - q[0] >= k) {
            q.shift()
        }
        // i >= k - 1 表示窗口已经形成,记录最大值
        if (i >= k - 1) {
            res.push(nums[q[0]])
        }
    }
    return res
};