《剑指offer第二版》面试题59: 队列的最大值（java）

题目描述

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

解题思路

1. 定义一个双端队列D。D中保存数组里数字对应的下标。
2. 先遍历第一个滑动窗口里的数字，将第一个滑动窗口里的最大值的下标放到D中。此时D的队首元素即为第一个滑动窗口的最大值的下标。
3. 继续遍历剩下的数字。假设当前遍历的数字值为A.
   1. 删除D中已经不再滑动窗口里的数字下标。
   2. 如果D的队尾元素对应的数字，小于或等于当前遍历的数字A，则删除D的队尾元素。如此反复，直到D中元素对应的值没有比A小的。
   3. 将A插入到D的队尾。
   4. 此时D的队首元素即为当前滑动窗口的最大值。

代码

List<Integer> maxInWindows(List<Integer> list, int size){
    if(list == null || list.size() <= 0 || size <= 0) {
        return null;
    }
    List<Integer> result = new ArrayList<>(); // 用于保存最终的结果

    Deque<Integer> index = new LinkedList<>();
    // 先找出第一个滑动窗口里的最大值
    for (int i = 0; i < size; i++) {
        if (!index.isEmpty() && list.get(i) >= list.get(index.peek())) {
            index.poll();//移除队首元素
        }
        index.offer(i); //向队尾插入元素
    }
    result.add(list.get(index.peek())); // 将第一个滑动窗口里的最大值添加到结果中
    for (int i = size; i < list.size(); i++) {
        index.remove(i - size); //移除已经不再滑动窗口内的元素
        while (!index.isEmpty() && list.get(i) >= list.get(index.peekLast())) {
            index.pollLast(); //移除队尾元素
        }
        index.offer(i);//向队尾插入元素
        result.add(list.get(index.peek()));
    }
    return result;
}