Sliding Window Maximum Solved in O(N) Using a Monotonic Deque

LeetCode's Sliding Window Maximum problem asks for the largest element in every contiguous subarray of size k. A brute-force approach scans each window fully, resulting in O(N×K) time complexity. The optimal solution uses a monotonic decreasing deque that stores indices, ensuring each element is inserted and removed at most once. The deque's front always holds the index of the current window's maximum, yielding O(N) time and O(K) space. This pattern generalizes to related problems like Sliding Window Minimum and Shortest Subarray with Sum at Least K.