Run, Hongjun
InterviewTime limit2sMemory limit256 MB
Given N billboard intensities and a sight range M, output the maximum intensity within a sliding window of size 2M-1 for each valid position.
- Level
Medium5 of 10
- Topics
- Sliding window, Queue, Array
- Solved
- No attempts yet
Problem
Hongjun runs at a constant speed, moving exactly one cell every second.
Each cell of the course has one billboard with a fixed light intensity. When Hongjun is on a cell, he can see billboards up to M - 1 cells behind him and M - 1 cells ahead of him. Among the billboards he can see, only the one with the greatest light intensity catches his eye.
Suppose Hongjun starts at the M-th cell and stops at the N - M + 1-th cell, moving one cell at a time. Output the greatest billboard light intensity he can see at each position, in order.
Input
The first line contains the course length N, the number of cells, and Hongjun's sight range M. A sight range of M means that from the current position he can see up to M - 1 cells in both directions, for a total visible range of 2M - 1 cells.
The second line contains the light intensities A_1, A_2, ..., A_N of the billboards in each cell.
1 <= M <= N <= 1,000,000- Each light intensity is a positive integer not greater than
1,000,000.
Output
Print, separated by spaces, the maximum billboard light intensity visible at each position as Hongjun moves from the M-th cell through the N - M + 1-th cell.