滑动窗口的最大值

发表于 | 分类于

题目

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在
6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}，
{2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路

用队列来模拟窗口
同时，利用两个栈来模拟队列可以降低复杂度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function maxInWindows(num, size)
{
    let res = [];
    if(size == 0){
        return res;
    }
    let begin;
    let queue = [];
    for(let i = 0; i < num.length; i++){
        begin = i - size + 1;//代表滑动窗口的左边界
        if(queue.length == 0){
            queue.push(i);
        }else if(begin > queue[0]){
            queue.shift();
        }
        while((queue.length != 0) && (num[queue[queue.length - 1]] <= num[i])){
            queue.pop();
        }
        queue.push(i);
        if(begin >= 0){
            res.push(num[queue[0]])
        }
    }
    return res;
}