Sliding Window Maximum
Problem Description
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 maximum element in each sliding window.
Examples
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
Input: nums = [1], k = 1
Output: [1]
Explanation: There is only one element in the window.
Input: nums = [1,-1], k = 1
Output: [1,-1]
Explanation: Each element appears in exactly one window.
Starter Code
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
# Write your code here
passHints
- How about using a data structure that can efficiently find the maximum element in a range?
- A deque (double-ended queue) can be used to maintain candidates for maximum elements
- Think about what elements in the window can never be the maximum