剑指offer第六十四题。

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

解题思路

比较简单的思路是每次用一个ArrayList来存放窗口内的数，进行排序，然后得到最大的添加进外面的ArrayList中，最后返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        List<Integer> result = new ArrayList<>();
        if(num.length == 0 || size == 0)
            return (ArrayList)result;
        for(int i=0;i<=num.length-size;i++){
            List<Integer> list = new ArrayList<>();
            for(int j=i;j<i+size;j++){
                list.add(num[j]);
            }
            Collections.sort(list);
            result.add(list.get(size-1));
        }
        return (ArrayList)result;
    }
    
}

遍历再排序，时间复杂度还是挺高的，遍历一遍是不可避免的，优化点在于如何以O(1)的时间复杂度拿到当前窗口的最大值。下面介绍一下优化方法。

以输入数字{2,3,4,2,6,2,5,1}为例一步分析。

数组的第一个数字是 2，把它存入队列中。第二个数字是3.由于它比前一个数字 2 大，因此 2不可能成为滑动窗口中的最大值。2 先从队列里删除，再把3存入到队列中。此时队列中只有一个数字 3。针对第三个数字 4 的步骤类似，最终在队列中只剩下一个数字 4。此时滑动窗口中已经有 3 个数字，而它的最大值 4 位于队列的头部。

接下来处理第四个数字 2。2 比队列中的数字 4 小。当 4 滑出窗口之后 2 还是有可能成为滑动窗口的最大值，因此把 2 存入队列的尾部。现在队列中有两个数字 4 和 2，其中最大值 4 仍然位于队列的头部。

下一个数字是 6。由于它比队列中已有的数字 4 和 2 都大，因此这时 4 和 2 已经不可能成为滑动窗口中的最大值。先把 4 和 2 从队列中删除，再把数字 6 存入队列。这个时候最大值 6 仍然位于队列的头部。

第六个数字是 2。由于它比队列中已有的数字 6 小，所以 2 也存入队列的尾部。此时队列中有两个数字，其中最大值 6 位于队列的头部。

接下来的数字是 5。在队列中已有的两个数字 6 和 2 里，2 小于 5，因此 2 不可能是一个滑动窗口的最大值，可以把它从队列的尾部删除。删除数字 2 之后，再把数字 5 存入队列。此时队列里剩下两个数字 6 和 5，其中位于队列头部的是最大值 6。

数组最后一个数字是 1，把 1 存入队列的尾部。注意到位于队列头部的数字 6 是数组的第 5 个数字，此时的滑动窗口已经不包括这个数字了，因此应该把数字 6 从队列删除。那么怎么知道滑动窗口是否包括一个数字？应该在队列里存入数字在数组里的下标，而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时，这个数字已经从滑动窗口中滑出，可以从队列中删除了。

image

框框里的都是下标。

我的答案

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
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        //存放当前窗口中最大值
        ArrayList<Integer> res = new ArrayList<>();
        //队列的头部存放的是当前窗口最大值
        LinkedList<Integer> queue = new LinkedList<>();
        if(num == null || num.length <= 0 || size <= 0){
            return res;
        }
        
        for(int i=0;i<num.length;i++){
            //比如当前数据比队尾的数字大，说明当前这个数字最起码在从现在起到后面的过程中可能是最大值
            //而之前队尾的数字不可能最大了，所以要删除队尾元素。
            while(!queue.isEmpty() && num[queue.peekLast()] < num[i]){
                queue.pollLast();
            }
            queue.add(i);
            //队头的元素是否超过窗口的范围
            if(queue.peekFirst() == i-size){
                queue.pollFirst();
            }
            //在包含了三个元素之后才开始记录，其中最大值就在队列的头部
            if(i >= size - 1){
                res.add(num[queue.peekFirst()]);
            }
        }
        return res;
    }
}