# Leetcode: Sliding Window Maximum

Sliding Window Maximum

Similar Problems:

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.

For example,

```Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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
Therefore, return the max sliding window as [3,3,5,5,6,7].
```

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

Could you solve it in linear time?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/sliding-window-maximum
## Basic Ideas: sliding window with decreasing sequence
##
## Complexity: Time O(n), Space O(k)
class Solution:
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
import collections
res = []
queue = collections.deque()
for i in range(len(nums)):
# remove the number
if len(queue)!=0 and queue[0] == i-k:
queue.popleft()

# keep the window decreasing
while len(queue) != 0 and nums[i] >= nums[queue[-1]]:
queue.pop()

# we need to add the new number in all cases
queue.append(i)