# Python solution with detailed explanation

• Solution

Sliding Window Maximum https://leetcode.com/problems/sliding-window-maximum/

Brute Force: O(n * k)

``````class Solution(object):
def get_max(self, nums, start, end):
for i in range(start, end+1):

def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
start,end = 0,k-1
result = []
while end < len(nums) and len(nums):
result.append(self.get_max(nums, start, end))
start, end = start+1, end+1
return result
``````

Max Heap Solution: O(NlogN)

• Add k elements and their indices to heap. Python has min-heap. So for max-heap, multiply by -1.
• Set start = 0 and end = k-1 as the current range.
• Extract the max from heap which is in range i.e. >= start. Add the max to the result list. Now add the max back to the heap - it could be relevant to other ranges.
• Move the range by 1. Add the new last number to heap.
• This is an O(NlgN) solution.
• Note that we need not invest into thinking about deleting the obsolete entry every time the window slides.That would be very hard to implement. Instead we maintain the index in heap and "delete" when the maximum number is out of bounds.
``````import heapq as h
class Solution(object):
def get_next_max(self, heap, start):
while True:
x,idx = h.heappop(heap)
if idx >= start:
return x*-1, idx

def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if k == 0:
return []
heap = []
for i in range(k):
h.heappush(heap, (nums[i]*-1, i))
result, start, end = [], 0, k-1
while end < len(nums):
x, idx = self.get_next_max(heap, start)
result.append(x)
h.heappush(heap, (x*-1, idx))
start, end = start + 1, end + 1
if end < len(nums):
h.heappush(heap, (nums[end]*-1, end))
return result
``````

Solution Using Dequeue: O(N)

*So, to maintain the queue in order,

• When moves to a new number, iterate through back of the queue, removes all numbers that are not greater than the new one, and then insert the new one to the back.
• findMax only need to take the first one of the queue.
• To remove a number outside the window, only compare whether the current index is greater than the front of queue. If so, remove it.*
``````from collections import deque
class Solution(object):
while len(dq) and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
return

def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if k == 0:
return []
dq = deque()
for i in range(k):
result, start, end = [], 0, k-1
while end < len(nums):
while True:
if dq[0] >= start:
result.append(nums[dq[0]])
break
else:
dq.popleft()
start, end = start+1,end+1
if end < len(nums):