Practice/Meta/Leetcode 239. Sliding Window Maximum

Leetcode 239. Sliding Window Maximum

CodingMust

Problem

You are given an array of integers nums and an integer k representing the size of a sliding window. The window starts at the leftmost position and slides one position to the right at a time until it reaches the end of the array.

For each position of the sliding window, you need to find the maximum value among the k elements currently in the window.

Return an array containing the maximum value for each window position.

Requirements

1. Process each window position from left to right
2. Return an array where each element is the maximum of one window position
3. The output array should have length n - k + 1 where n is the length of the input array
4. Handle negative numbers correctly

Constraints

• 1 ≤ nums.length ≤ 100,000
• -10,000 ≤ nums[i] ≤ 10,000
• 1 ≤ k ≤ nums.length
• Expected time complexity: O(n)
• Expected space complexity: O(k)

Examples

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] Explanation: Single element array with window size 1 returns that element.

Example 3:

Input: nums = [9, 10, 9, -7, -4, -8, 2, -6], k = 5 Output: [10, 10, 9, 2] Explanation: The maximum of each 5-element window as it slides through the array.