[FEATURE]Add Sliding Window Maximum algorithm using Deque
I would like to propose adding an implementation of the Sliding Window Maximum algorithm in C++ using a Deque (monotonic deque technique).
Given an array and a window size K, this algorithm efficiently finds the maximum element in every contiguous window of size K as it slides across the array, in O(N) time instead of the naive O(N*K) brute-force approach.
How the Algorithm Works:
Maintain a deque that stores indices of array elements, kept in decreasing order of their values. For each new element: Remove indices from the back of the deque whose values are smaller than the current element (they can never be the max while the current element is in the window). Remove the index at the front if it has slid out of the current window. Push the current index to the back. Once the first window is filled, the front of the deque is the maximum for that window.
Proposed Changes:
Add sliding_window_maximum.cpp under data_structures/ (or others/, whichever fits the existing structure best - open to maintainer guidance on placement) Complete implementation using std::deque to maintain indices of useful elements Clear comments explaining the monotonic deque invariant Self-tests within the file (following the repo's existing style of in-file assertion-based tests) covering standard cases, K equal to array size, K = 1, and duplicate elements
Complexity Analysis:
Time Complexity: O(N) -- each element is pushed and popped from the deque at most once Space Complexity: O(K) -- the deque holds at most K indices at a time
I will ensure the implementation follows the repository's coding style (clang-format/clang-tidy) and passes CI before opening a PR. I'll go ahead and start working on this and open a PR referencing this issue.
Source: TheAlgorithms/C-Plus-Plus