161. Window Peaks
A weather station records the temperature once per hour and stores the readings in the array nums. A forecaster looks through a frame that is exactly k consecutive hours wide and slides it from the start of the record to the end, moving one hour at a time.
For every position of the frame, find the highest reading currently inside it. Return an array holding these peaks in order, from the first frame position to the last. The array has nums.length - k + 1 entries, and the order is fixed, so it must match exactly.
Example 1
- Input:
- nums = [4,1,6,2,2,5], k = 3
- Output:
- [6,6,6,5]
- Explanation:
The frames are [4,1,6], [1,6,2], [6,2,2] and [2,2,5], whose peaks are 6, 6, 6 and 5.
Example 2
- Input:
- nums = [-3,-7,-1], k = 2
- Output:
- [-3,-1]
- Explanation:
The frames are [-3,-7] and [-7,-1], with peaks -3 and -1. Negative readings work the same way.
Example 3
- Input:
- nums = [9], k = 1
- Output:
- [9]
- Explanation:
There is a single frame holding one reading, so the answer is [9].
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i] ≤ 109
1 ≤ k ≤ nums.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(k)