## Description

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[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


Note: You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up: Could you solve it in linear time?

## Solutions

### 1. Two-End Queue

# Time: O(n)
# Space: O(n)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums:
return []
n = len(nums)
if n <= k:
return [max(nums)]
res = []
# the front of the two-end queue stores the max in the window
qmax = []
for i in range(n):
if not qmax:
qmax.insert(0, i)
elif nums[i] < nums[qmax[-1]]:
qmax.append(i)
else:
while qmax and nums[i] >= nums[qmax[-1]]:
qmax.pop()
qmax.append(i)
if i >= k-1:
while qmax and i - qmax[0] + 1 > k:
qmax.pop(0)
res.append(nums[qmax[0]])
return res
# 18/18 cases passed (184 ms)
# Your runtime beats 54.31 % of python3 submissions
# Your memory usage beats 80.77 % of python3 submissions (19.6 MB)


自己实现的太多 if-else 了，优化一下，更优雅一些：

# Time: O(n)
# Space: O(n)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums:
return []
n = len(nums)
if n <= k:
return [max(nums)]
res = []
# the front of the two-end queue stores the max in the window
qmax = []
for i in range(n):
while qmax and nums[i] > nums[qmax[-1]]:
qmax.pop()
qmax.append(i)
if i >= k - 1:
while qmax and i - qmax[0] + 1 > k:
qmax.pop(0)
res.append(nums[qmax[0]])
return res
# 18/18 cases passed (180 ms)
# Your runtime beats 61.53 % of python3 submissions
# Your memory usage beats 80.77 % of python3 submissions (19.6 MB)


### 2. Array

操作数组：

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums: return([])

max_cur = max(nums[:k])

ans = [max_cur]
for i,j in enumerate(nums):
if i>=k:
if j>=max_cur:
max_cur = max([max_cur,j])
ans.append(max_cur)
else:
if nums[i-k]<max_cur:
ans.append(max_cur)
else:
max_cur = max(nums[i-k+1:i+1])
ans.append(max_cur)
return(ans)