Sliding Window
LC #239Hard
Sliding Window Maximum
Sliding Window
AmazonGoogleMetaMicrosoftBloombergProblem
Return the maximum value in each sliding window of size k as it moves across the array.
sliding-windowdequemonotonic
Constraints
- ›1 ≤ nums.length ≤ 10⁵
- ›-10⁴ ≤ nums[i] ≤ 10⁴
- ›1 ≤ k ≤ nums.length
Example
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3Output
[3,3,5,5,6,7]Why
Max of each window: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5, [-3,5,3]=5, [5,3,6]=6, [3,6,7]=7