求解代码
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class MonotonicQueue {
LinkedList<Integer> queue = new LinkedList<>();
public void push(int n){
while(!queue.isEmpty()&&queue.getLast()<n){
queue.pollLast();
}
queue.addLast(n);
}
public void pop(int n){
if(n==queue.getFirst()){
queue.pollFirst();
}
}
public int max(){
return queue.getFirst();
}
}
public ArrayList<Integer> maxInWindows (int[] num, int size) {
MonotonicQueue window = new MonotonicQueue();
ArrayList<Integer> res = new ArrayList<>();
if(num==null||size<=0||num.length==0||size>num.length){
return res;
}
for(int i=0;i<num.length;i++){
if(i<size-1){
window.push(num[i]);
}else{
window.push(num[i]);
res.add(window.max());
window.pop(num[i-size+1]);
}
}
return res;
}
|
小贴士
1.构建一个特殊的【单调队列】来充当不断滑动的窗口：
这个单调队列的队首记录了滑动过程中的最大值（对应max方法），从队首到队尾的元素值大小是单调递减的；
当队列为空或者尾部的元素（getLast）小于要入队的元素时，将该尾部元素弹出（pollLast）,元素是从队列尾部入队的（addLast）。
当滑动窗口需要移除的元素等于队列头部（当前最大值）时，将队首元素弹出（pollFirst）；
2.解释一下这个i-size+1
对于长度固定为size的滑动窗口，当窗口还没填满时，不考虑计算最大值和移除元素，直到把前size-1个元素填满；
从第size个元素开始（对应就是下标size-1），窗口正式填满，此时，依次完成把当前元素加入窗口，将窗口的最大值记录到res中，再把窗口最左侧的元素移除，为下一步滑动腾出一个位置。
那窗口最左侧元素的下标是什么呢？
因为当前元素是num[i]，所以此时的窗口的右边界是i，又因为窗口的大小固定为size，所以，窗口的左边界就是i-size+1，这也就是我们要移除的窗口最左侧元素的下标。