滑动窗口中的最大值

题目

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。 以数组为[4,3,5,4,3,3,6,7]，w=3为例。因为第一个窗口[4,3,5]的最大值为5，第二个窗口[3,5,4]的最大值为5，第三个窗口[5,4,3]的最大值为5。第四个窗口[4,3,3]的最大值为4。第五个窗口[3,3,6]的最大值为6。第六个窗口[3,6,7]的最大值为7。所以最终返回[5,5,5,4,6,7]。
给定整形数组arr及它的大小n，同时给定w，请返回res数组。保证w小于等于n，同时保证数组大小小于等于500。

测试样例：[4,3,5,4,3,3,6,7],8,3
返回：[5,5,5,4,6,7]

思路

用双端队列deque保存可能成为滑动窗口中最大元素的下标，进出队列规则如下：

1. 如果deque为空，直接将下标i放入deque中。
2. 如果当前下标i-队头元素==w,弹出队头元素。
3. 如果deque不为空，取出deque队尾的下标j，如果arr[j]>=arr[i],将下标i放入deque队尾。否则依次弹出队尾元素，直到arr[j]<arr[i]或者deque为空，再将i压入队尾。

1和2都比较好理解，这里解释一下3:

如果arr[j]>=arr[i],将下标i放入deque队尾。否则依次弹出队尾元素，直到arr[j]<arr[i]或者deque为空，再将i压入队尾.

arr[j]>=arr[i],为什么要放在队尾呢，arr[i]虽然此时比arr[j]小，但是arr[j]会在一定时间后失效(即脱出滑动窗口范围),arr[i]可能会成为最大值。
而当arr[j]<arr[i],说明arr[j]永远不能成为当前窗口及以后窗口的最大值了，因为arr[j]不仅比arr[i]小，而且一定比arr[j]先失效。所以将其弹出即可。

当初始队列构造完成后，依次读入数组元素，队列的头元素的下标所代表的数字就是此时窗口中的最大值。

代码

import java.util.*;

public class SlideWindow {
    public int[] slide(int[] arr, int n, int w) {
        
        int[]result=new int[n-w+1];
        Deque<Integer> window=new ArrayDeque<>();
        //初始化宽度为w的滑动窗口
        int i=0;
        for(;i<w;i++){
            if(!window.isEmpty()&&arr[i]>arr[window.getLast()]){
                while(!window.isEmpty()&&arr[window.getLast()]<arr[i]){
                    window.removeLast();
                }
            } 
            window.addLast(i);
        }
        int size=0;
        result[size]=arr[window.getFirst()];
        
        //依次进行滑动
        for(;i<n;i++){
            if(i-window.getFirst()==w){
                window.removeFirst();
            }
            
            if(!window.isEmpty()&&arr[i]>arr[window.getLast()]){
                while(!window.isEmpty()&&arr[window.getLast()]<arr[i]){
                    window.removeLast();
                }
            } 
            window.addLast(i);
            result[++size]=arr[window.getFirst()];
        }
        return result;
    }
}