Sliding Window Maximum
JavaScript
Hard
5 views
Problem Description
Given n numbers and window size k, print the maximum for each window.
Input Format
Line1: n k. Line2: n integers.
Output Format
n-k+1 integers space separated.
Sample Test Case
Input:
8 3
1 3 -1 -3 5 3 6 7
Official Solution
const fs=require('fs');const raw=fs.readFileSync(0,'utf8').trim();if(!raw)process.exit(0);const a=raw.split(/\\s+/).map(Number);let i=0;const n=a[i++],k=a[i++];const arr=a.slice(i,i+n);const dq=[];let head=0;const out=[];for(let j=0;j<n;j++){while(dq.length>head && arr[dq[dq.length-1]]<=arr[j])dq.pop();dq.push(j);if(dq[head]<=j-k)head++;if(j>=k-1)out.push(arr[dq[head]]);}process.stdout.write(out.join(' '));
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!