【链表】打卡1：生成窗口最大值数组

做算法题了，题的难度我们分为“士，尉，校，将”四个等级。这个算法题的模块是篇幅比较小的那种模块。首先是给出一道题的描述，之后我会用我的想法来做这道题，今天算是算法题的第一道题，先来试试水。

问题描述（等级：尉）

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。

例如，数组为[4,3,1,5,4,3,7,5]，窗口大小为5时:

[4 3 1 5 4] 3 7 5 　max = 5

4 [3 1 5 4 3] 7 5 　max = 5

4 3 [1 5 4 3 7] 5 　max = 7

4 3 1 [5 4 3 7 5] 　max = 7

即窗口最大值数组为 result = {5, 5,7,7}

解答

对于一道题，我一般会第一时间想到用暴力的方法来做，之后再来慢慢优化。

显然，对于这道题用暴力法来做还是挺简单了，窗口每次向右移动一位时，我们每次遍历窗口内的w个元素，然后求出此时窗口的最大值就可以了，用这种方法的时间复杂度是 O(w*n)。代码如下：

//暴力法求解，时间复杂度：O(n*w)
//w:窗口内的w个元素
public static int[] getMaxWindow(int[] arr,int w){
    int length = arr.length;
    if(w<1 || arr == null || length<w){
        return null;
    }
    int[] result = new int[length-w+1];
    int index = 0;
    //总共需要遍历result.length，也就是length-w+1次
    for (int i = w-1; i < length; i++) { 
        int max = arr[i];
        //暴力求解直接从第 w-1个元素开始遍历
        for (int j = i; j > i-w; j--) {
            if(arr[j]>max){
                max = arr[j];
            }
        }
        result[index++] = max;
    }
    return result;
}

大家想一个问题，例如对于刚才例题中的数组：

第一次遍历的时候，max = 5

第二次遍历的时候，max = 5

我们刚才用暴力法的时候，无论是第一次还是第二次，我们都是把窗口内的所有元素都给遍历了一次，以此来寻找最大值，可是，真的需要这样吗？

第一次遍历的时候，我们找出了max = 5, 那么在第二次遍历的时候，在窗口范围内，max = 5 左边的两个数1， 3 还有可能是最大值吗？也就是说，max=5 左边的窗口元素还要必要遍历吗？

显然，max=5左边的窗口实际上是不必再遍历的了，也就是它不可能会是窗口的最大值。

而 max = 5 右边的 4 有可能会是窗口的最大值吗？由于窗口还会一直向右移动，所以 max = 5 右边的窗口元素还是有可能是某一个窗口的最大值的。

因此，我们可以用一个双向的队列，来记录有可能成为窗口最大值的下标，注意，这里指的是有可能。

像刚才的 max = 5 前面的 1,3 就不可能成为窗口的最大值了，而右边的4还是有可能成为窗口的最大值的。并且这个队列是有序的，队首存放的总是队列中的最大值，

我以这道题来演示一下，我们用result[] 数组来存放窗口最大值。

1、result[0] = 5

2、result[1] = 5;

3、result[2] = 7

其他的全部都要出队，因为7前面的5，4，3是不可能成为窗口最大值的了。

4、result[3] = 7

遍历完毕。这种方法的话时间复杂度是 O(n)。

我这里只是提供了思路与大致的做法，具体的代码实现还是有很多细节需要注意的。下面给出实现代码，代码会有详细的解释。

//优化，时间复杂度：O(n)
public static int[] getMaxWindow2(int[] arr,int w){
    int length = arr.length;
    if(w<1 || arr == null || length<w){
        return null;
    }
    //用来保存成为最大窗口的元素
    int[] result = new int[length-w+1];
    int index = 0;
    //用链表充当双向队列
    LinkedList<Integer> tempList = new LinkedList<Integer>();
    //暴力法直接从i=w-1开始的
    for (int i = 0; i < length; i++) {
        /*如果队列不为空，并且存放在队尾的元素小于等于当前元素，那么 
        队尾的这个元素就可以弹出了，因为他不可能会是窗口最大值。
		当前元素指的是i增大时新加入的元素。*/
        //经过检测，比较队首的元素也是可以的
        while(!tempList.isEmpty() && arr[tempList.peekFirst()]<arr[i]){
            tempList.pollFirst();
        }
        //把当前元素的下标加入队尾
        tempList.addLast(i);
        //如果队首的元素的下标不在窗口范围内，则弹出
        if(tempList.peekFirst() == i-w){
            tempList.pollFirst();
        }
        //由于队首存放的是最大值，所以队首总是对应窗口的最大值元素
        if(i>=w-1){
            result[index++] = arr[tempList.peekFirst()];
        }
    }
    return result;
}

说实话，微信看代码确实有点难受，如果是在电脑浏览的话还好点，我在考虑要不要用截图的方式，不过如果是截图的话，有些人想要复制代码的话会复制不了，那我之后考虑把代码打包，你们后台回复获取。

来源：苦逼的码农（ID:di201805）

（完）