AcWing 154. 滑动窗口 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-20 13:54:56
,
所有人可见
,
阅读 833
let inArr = [];
let min = [], max = [];
let n = 0, k = 0;
let queue = new Array(100010);
let head = 0, tail = -1;
let push = x => queue[++tail] = x;
let checkMin = () => {
head = 0, tail = -1;
for (let i = 0; i < n; i++) {
// 是否在窗口内
if (head <= tail && i - k + 1 > queue[head])++head;
//剔除比 i 大的元素
while (head <= tail && inArr[i] <= inArr[queue[tail]])--tail;
//经过以上步骤 i处必然小于tail
push(i);
//滑动窗口从k-1才开始比较
if (i >= k - 1) min.push(inArr[queue[head]]);
}
}
let checkMax = () => {
head = 0, tail = -1;
for (let i = 0; i < n; i++) {
if (head <= tail && i - k + 1 > queue[head])++head;
while (head <= tail && inArr[i] >= inArr[queue[tail]])--tail;
push(i);
if (i >= k - 1) max.push(inArr[queue[head]]);
}
}
let buf = '';
process.stdin.on('readable', () => {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputArgs = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
process.stdin.on('end', () => {
buf.split('\n').forEach((line, lineIdx) => {
if (lineIdx === 0) {
let a = getInputArgs(line);
n = a[0], k = a[1];
} else if (lineIdx === 1) {
inArr = getInputArgs(line);
checkMin();
checkMax();
console.log(min.join(' '));
console.log(max.join(' '));
}
});
});