239. Sliding Window Maximum
使用一个双向队列储存当前窗口的最大值候选者,最大值放在队首
const maxSlidingWindow = function (nums, k) {
const doubleQueue = [],
res = [];
for (let i = 0, ii = nums.length; i < ii; ++i) {
// 如果当前队首的值已经不在滑动窗口了,移除它
if (doubleQueue.length !== 0 && doubleQueue[0] < i - k + 1) {
doubleQueue.shift();
}
// 当滑动窗口右移的时候,要将当前i放到队列中,把队列中小于nums[i]的都删掉(从后向前找)
while (doubleQueue.length !== 0 && nums[doubleQueue[doubleQueue.length - 1]] < nums[i]) {
doubleQueue.pop();
}
doubleQueue.push(i);
if (i >= k - 1) {
res[i - k + 1] = nums[doubleQueue[0]];
}
}
return res;
};