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;
};
Python3:
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
但是如果真的是这样，这道题也不会是 hard 吧？这道题有一个 follow up，要求你用线性的时间去完成。
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;
};
复杂度分析
时间复杂度：$O(N * k)$，如果使用双端队列优化的话，可以到 $O(N)$
空间复杂度：$O(k)$
Python3:
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
