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): answer = -2**31 for i in range(start, end+1): answer = max(answer, nums[i]) return answer 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)
- Very similar code structure to heap solution
- Add to dequeue at tail using the rule where you pop all numbers from tail which are less than equal to the number. Think why? 300->50->27 and say 100 comes. 50 and/or 27 can never be the maximum in any range.
- When you do the above, the largest number is at head. But you still need to test if front is within the range or not.
- Pop or push each element at-max once. 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): def add_to_dq(self, dq, nums, i): 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): self.add_to_dq(dq, nums, i) result, start, end = , 0, k-1 while end < len(nums): while True: if dq >= start: result.append(nums[dq]) break else: dq.popleft() start, end = start+1,end+1 if end < len(nums): self.add_to_dq(dq, nums, end) return result