Sliding Window Maximum

Hard

Sliding Window

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^5
•-10^4 <= nums[i] <= 10^4
•1 <= k <= nums.length

Show Hints (4)

Hint 1: Use a deque (double-ended queue) to store indices.

Hint 2: Keep the deque in decreasing order of values.

Hint 3: Remove indices that are out of the current window.

Hint 4: The front of the deque always contains the maximum for the current window.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?