239. Sliding Window Maximum.md

239. Sliding Window Maximum (Hard)

[tag] two pointers, deque, queue

• Use a deque for store numbers in decreasing order.
• when first number is out of range, pop.
• ans is the first number in the deque,

'''
[1,3,-1,-3,1,3,6,7]
      i
i = 2
max_deque: 1 2
ans: 
'''
# Using while loop
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # store index
        max_deque = deque()
        ans = []
        l = r = 0
        while r < len(nums):
            while max_deque and nums[max_deque[-1]] < nums[r]:
                max_deque.pop()
            max_deque.append(r)
            # if left is out of bound, remove it.
            if l > max_deque[0]:
                max_deque.popleft()
            if r >= k-1:
                ans.append(nums[max_deque[0]])
                l += 1
            r += 1
        return ans