# 239. Sliding Window Maximum

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position.

For example,
Givennums=`[1,3,-1,-3,5,3,6,7]`, andk= 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 assumekis always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Could you solve it in linear time?

Thoughts:

1. O(nlogk): Maintain a max heap of k elements
2. O(n): Have a deque to keep track of current window maximum

Code: Heap

``````public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
int[] result = new int[len - k + 1];
if(nums.length == 0) return new int[0];
Queue<Integer> queue = new PriorityQueue<Integer>((n1, n2) -> n2 - n1);

int i = 0;
for(; i < k; i ++) queue.add(nums[i]);

result[i - k] = queue.peek();

for(; i < len; i ++){
queue.remove(nums[i - k]);
result[i - k + 1] = queue.peek();
}

return result;
}
}
``````

Code

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.empty() || k <= 0) return nums;
int n = nums.size();
vector<int> windowMax;
deque<int> dq;
for(int i = 0; i < nums.size(); i ++){
// check in the range
while(!dq.empty() && dq.front() < i - k  + 1){
dq.pop_front();
}
// remove smaller numbers in k range as they are useless
while(!dq.empty()&& nums[dq.back()] < nums[i]){
dq.pop_back();
}
dq.push_back(i);
if(i >= k - 1){ windowMax.push_back(nums[dq.front()]);}
}
return windowMax;
}

};
``````

Python

``````class Solution(object):
def maxSlidingWindow(self, nums, k):
d = collections.deque()
out = []
for i, n in enumerate(nums):
while d and nums[d[-1]] < n:
d.pop()
d += i,
if d[0] == i - k:
d.popleft()
if i >= k - 1:
out += nums[d[0]],
return out
``````

Special Thanks to flyingpenguin and jianchaolifighter for the reference