PHP Program to Sliding Window Maximum with Explanation
PHP
Hard
PHP Arrays
40 views
1 min read
101 words
This problem helps you practice core PHP fundamentals in a practical way. It builds intuition around sliding window, window, maximum. Let’s break it down step by step so you can implement it confidently.
Problem Statement
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.
Constraints
n
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
<?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);
?>
Output Example
Input:
8 3
1 3 -1 -3 5 3 6 7
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Solution Guide
Problem
Given array and window size k, print the maximum in each window.
Input / Output
Input
Line1 n k. Line2 n ints.
Output
One line n-k+1 ints.
Examples
Input:
8 3
1 3 -1 -3 5 3 6 7
Details
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
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!
