leetcode 239 滑动窗口最大值

题目

给你一个整数数组 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]
示例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2
输出：[11]
示例 5：
输入：nums = [4,-2], k = 2
输出：[4]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1.双端队列
变量 window = [] res = []
维护窗口
1.维护窗口左端为最大值，即使得窗口为单调递减队列
2.窗口长度=== k 时，需要先将窗口左端点出列
3.维护单调递减队列：当遍历到的nums[i]值>=window[-1]时，window[-1]出队
4.当i>=k-1时，记录最大值（左端点）
时间复杂度 O（kn）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = function (nums, k) {
    // 维护窗口【0】号位置一直是最大
    //即 只要 维护窗口时单调递减即可
    const n = nums.length
    const res = [],
        window = []
    for (let i = 0; i < n; i++) {
        const v = nums[i]
        if (i >= k && window[0] <= i - k) { // 说明此时窗口左侧元素超出范围
            window.shift()
        }
        while (window.length > 0 && v >= nums[window[window.length - 1]]) {
            window.pop()
        }
        window.push(i)
        if (i >= k - 1) {
            res.push(nums[window[0]])
        }
    }
    return res
};

2.大根堆
大根堆对于最大值一直是一种非常好的数据结构
但是由于js没有现成的数据结构，这里需要手写
注意点：由于大根堆的最大值可能会超出左边界范围，所以需要永久移除，这里的方法是建立二元组进行移除

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        res = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            res.append(-q[0][0])
        return res