hardSliding WindowPattern: Sliding Window / Monotonic Deque
Consecutive Maximum Values Solution
Problem Statement
Given an array of integers `values` and an integer `windowSize`, find the maximum value in every subarray of size `windowSize`.
Examples
Example 1:
Input:nums = [1,3,-1,-3,5,3,6,7], k = 3
Output:[3,3,5,5,6,7]
Explanation: For every window of k=3 consecutive readings, find the peak consumption.
Constraints
- 1 <= n <= 10^5
- 1 <= k <= n
- -10^4 <= arr[i] <= 10^4
Time: O(N) Space: O(K)
Use Deque. Store indices. Remove indices out of window bounds. Remove indices whose values are <= current value (they can never be max). Add current index. Deque front always holds max for current window. Time O(N), Space O(K).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.