Show problems as
Classic problem #239HardArrayQueueSliding WindowMonotonic Queue

Sliding Window Maximum

Real-world version: Rolling Peak Readings
Tracked in this browser only
Read Sliding Window Maximum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstSliding Window & Monotonic Queue · Stacks & Queues, animated step by step

A weather mast logs one temperature per minute for an entire shift. readings[i] is the whole-degree Celsius value captured during minute i; anything below freezing is negative.

The report generator studies blocks of span back-to-back minutes. The first block covers minutes 0 through span - 1. Each following block starts one minute later than the one before it, and the last block is the one whose final minute is the final minute of the shift. For every block the generator keeps a single number: the largest reading anywhere inside that block.

Return those block peaks, listed in the same order the blocks were studied. For n readings and a block of span minutes there are n - span + 1 peaks to report.

span is never smaller than 1 and never larger than the number of readings, so there is always at least one block. When span is 1 each block is a single minute, and when span equals the number of readings there is exactly one block covering the whole shift.

Examples

Example 1

Input
readings = [4, -1, 6, 6, 2, -3, 7], span = 3
Output
[6, 6, 6, 6, 7]

Five blocks of three minutes fit in seven readings. The two sixes keep the peak at 6 for the first four blocks, and once both have dropped out of view the last block peaks at 7.

Example 2

Input
readings = [9, 5, 1], span = 1
Output
[9, 5, 1]

Every block is one minute long, so each reading is its own peak and the output copies the input.

Example 3

Input
readings = [-8, -2, -5, -9], span = 4
Output
[-2]

The block width matches the shift length, so a single block covers all four minutes and its warmest reading is -2 degrees.

Constraints

  • 1 <= readings.length <= 10^5
  • -10^4 <= readings[i] <= 10^4
  • 1 <= span <= readings.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def rolling_peaks(readings: list[int], span: int) -> list[int]:
Java
public int[] rollingPeaks(int[] readings, int span)

More on the same topics