> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-24-2022-239.md).

# 01/24/2022 239

![](/files/JOofTBhyVYexpLJxJxwB)

Use deque to store the first k elemets. Then iterate over the array, at each step: Keep only the indexes of elements from the current sliding window;  Remove indexes of all elements smaller than the current one, since they will not be the maximum ones. Then append the current elements to the deque and append deque\[0] to the results. 

Time O(N)

Space O(N)

* Process the first `k` elements separately to initiate the deque.
* Iterate over the array. At each step :
  * Clean the deque :
    * Keep only the indexes of elements from the current sliding window.
    * Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.
  * Append the current element to the deque.
  * Append `deque[0]` to the output.
* Return the output array.