:orphan:

Sliding Window Maximum
======================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/sliding-window-maximum/

You are given an array of integers ``nums``, there is a sliding window
of size ``k`` which is moving from the very left of the array to the
very right. You can only see the ``k`` numbers in the window. Each time
the sliding window moves right by one position.

Return *the max sliding window*.

 

**Example 1:**

::


   Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
   Output: [3,3,5,5,6,7]
   Explanation: 
   Window position                Max
   ---------------               -----
   [1  3  -1] -3  5  3  6  7       3
    1 [3  -1  -3] 5  3  6  7       3
    1  3 [-1  -3  5] 3  6  7       5
    1  3  -1 [-3  5  3] 6  7       5
    1  3  -1  -3 [5  3  6] 7       6
    1  3  -1  -3  5 [3  6  7]      7

**Example 2:**

::


   Input: nums = [1], k = 1
   Output: [1]

 

**Constraints:**

- ``1 <= nums.length <= 10``\ :sup:```5```
- ``-10``\ :sup:```4```\ ``<= nums[i] <= 10``\ :sup:```4```
- ``1 <= k <= nums.length``

.. highlight:: python

Pattern
-------
Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue

Approaches
----------

.. tab-set::

    .. tab-item:: Monotonic Deque

        **Code**

        .. literalinclude:: ../problems/hard/sliding-window-maximum/sliding_window_maximum__monotonic_deque.py
            :language: python
            :lines: 9-

        **Test**

        >>> from sliding_window_maximum__monotonic_deque import maxSlidingWindow
        >>> maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)
        [3, 3, 5, 5, 6, 7]
        >>> maxSlidingWindow([1], 1)
        [1]

        .. autofunction:: sliding_window_maximum__monotonic_deque.maxSlidingWindow