Sliding Window Maximum
- 2 min read
- LC-Hard
- Sliding Window
3 years ago
Solution
- Use a Monotonic Queue (Decreasing). Store the index, not the actual number. This will make it easier to pop from the left once the sliding window goes past a previous maximum.
- The leftmost element at the queue will always be the highest. While iterating, only store elements in decreasing order. This way, we'll not only know the max of the sliding window, but also the max of the next sliding window after the left pointer increases.
- Whenever the left pointer moves after the index of the previous maximum, pop from the left of the queue to updated our maximum to the next in the queue
- CHECK THE LEFTMOST ELEMENT BEING OUTSIDE OF THE BOUNDS OF THE SLIDING WINDOW IMMEDIATELY AFTER APPENDING THE ELEMENT TO THE ANSWER!
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
ans = []
l = 0
for r in range(len(nums)):
while q and nums[q[-1]] < nums[r]:
q.pop()
q.append(r)
if r + 1 >= k:
ans.append(nums[q[0]])
l += 1
if l > q[0]:
q.popleft()
return ans