Leetcode #:239Name:Sliding Window MaximumDifficulty:HardUrl:https://leetcode.com/problems/sliding-window-maximum/

# Problem Statement

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

`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

Constraints

`1 <= nums.length <= 105`

`104 <= nums[i] <= 104`

`1 <= k <= nums.length`

# Approach

Brute Force: O(k * (n — k))

We can simply take the maximum of each sliding window of size k as we shift it by 1 until we scan the given array from left to right. The time complexity of this would be the size of the sliding window (k) * the number of sliding windows we are going to have (n — k).

Monotonically Decreasing Queue: O(n)

If we have a sliding window and we see a value that is greater than previous values in our window, then we can eliminate those previous values from our window.

# Code

# Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com