# 【基础篇 - Day 30】 2020-11-30 - 239. 滑动窗口最大值
# 题目描述
# 题目描述
给定一个数组 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^4 1 <= k <= nums.length来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sliding-window-maximum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
https://github.com/leetcode-pp/91alg-2/issues/59#issuecomment-741621933
# 解法一
# 时空复杂度
时间复杂度：O(n^2)
空间复杂度: O(n)
先来一手超出时间限制
var maxSlidingWindow = function (nums, k) {
let res = []
for (let i = k; i <= nums.length; i++) {
let window = nums.slice(i - k, i)
res.push(Math.max(...window))
}
return res
};
# 解法二
# 时空复杂度
时间复杂度：O(n)
空间复杂度: O(n)
维护一个类似于单调栈的单调队列，
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
class Dequeue {
constructor(nums = []) {
this.list = nums
}
shift(val) {
if (this.list[0] === val) this.list.shift()
}
push(val) {
while (this.list[this.list.length - 1] < val) {
this.list.pop()
}
this.list.push(val)
}
max() {
return this.list[0]
}
}
var maxSlidingWindow = function (nums, k) {
let res = []
let queue = new Dequeue()
for (let i = 0; i < k - 1; i++) {
queue.push(nums[i])
}
for (let i = k - 1; i < nums.length; i++) {
queue.push(nums[i])
res.push(queue.max())
queue.shift(nums[i - k + 1])
}
return res
};