题目地址(239. 滑动窗口最大值)

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

题目描述

给定一个数组 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^41 <= k <= nums.length

前置知识

• 队列

• 滑动窗口

公司

• 阿里

• 腾讯

• 百度

• 字节

思路

符合直觉的想法是直接遍历 nums, 然后然后用一个变量 slideWindow 去承载 k 个元素， 然后对 slideWindow 求最大值，这是可以的，遍历一次的时间复杂度是 $N$，k 个元素求最大值时间复杂度是 $k$， 因此总的时间复杂度是 O(n * k).代码如下：

#"false">

var maxSlidingWindow = function (nums, k) {  // bad 时间复杂度O(n * k)  if (nums.length === 0 || k === 0) return [];  let slideWindow = [];  const ret = [];  for (let i = 0; i < nums.length - k + 1; i++) {    for (let j = 0; j < k; j++) {      slideWindow.push(nums[i + j]);    }    ret.push(Math.max(...slideWindow));    slideWindow = [];  }  return ret;};

class Solution:    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:        if k == 0: return []        res = []        for r in range(k - 1, len(nums)):            res.append(max(nums[r - k + 1:r + 1]))        return res

var maxSlidingWindow = function (nums, k) {  // 双端队列优化时间复杂度, 时间复杂度O(n)  const deque = []; // 存放在接下来的滑动窗口可能成为最大值的数  const ret = [];  for (let i = 0; i < nums.length; i++) {    // 清空失效元素    while (deque[0] < i - k + 1) {      deque.shift();    }    while (nums[deque[deque.length - 1]] < nums[i]) {      deque.pop();    }    deque.push(i);    if (i >= k - 1) {      ret.push(nums[deque[0]]);    }  }  return ret;};

class Solution:    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:        q = collections.deque() # 本质就是单调队列        ans = []        for i in range(len(nums)):            while q and nums[q[-1]] <= nums[i]: q.pop() # 维持单调性            while q and i - q[0] >= k: q.popleft() # 移除失效元素            q.append(i)            if i >= k - 1: ans.append(nums[q[0]])        return ans