Sliding Window Maximum
PHP
Hard
5 views
Problem Description
Given array and window size k, print the maximum in each window.
Input Format
Line1 n k. Line2 n ints.
Output Format
One line n-k+1 ints.
Sample Test Case
Input:
8 3
1 3 -1 -3 5 3 6 7
Official Solution
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$i=0; $n=intval($tokens[$i++] ?? 0);
$k=intval($tokens[$i++] ?? 0);
$a=[];
for($t=0;$t<$n;$t++) $a[] = intval($tokens[$i++] ?? 0);
$deque=[]; $head=0;
$output=[];
for($i=0;$i<$n;$i++){
while(count($deque)>$head && $deque[count($deque)-1][0] <= $a[$i]) array_pop($deque);
$deque[] = [$a[$i],$i];
if($deque[$head][1] <= $i-$k) $head++;
if($i>=$k-1) $output[] = strval($deque[$head][0]);
}
echo implode(' ',$output);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!