[Sliding Window] Sliding Window Maximum

[sudosf]

Problem

Given an array and window size k, return the max value in each window as the window slides from left to right.

References

• LeetCode: https://leetcode.com/problems/sliding-window-maximum/
• GFG: https://www.geeksforgeeks.org/problems/maximum-of-all-subarrays-of-size-k3101/1
• Sheet: https://www.risingbrain.org/sheet#array (Sliding Window [Two Pointer] Sort Colors #7)
• Parent: Pattern: Sliding Window (Arrays) #10

Difficulty

🔴 Hard

Companies

Amazon, Google, DE Shaw

Notes

Language: Java
Naive O(nk) won't pass. Use a monotonic deque (ArrayDeque) for O(n).