队列的最大值.md

题目描述

滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。

测试用例

• 功能测试（输入数组的数字大小无序；输入数组额数字单调递增；输入数组的数字单调递减）
• 边界值测试（滑动窗口的大小为0、1、等于输入数组的长度、大于输入数组的长度）
• 特殊输入测试（输入数组为空）

题目考点

• 考察应聘者分析问题的能力。

解题思路

利用一个双端队列（存数组下标），并永远保持队首为最大值。

在过程中需要保证两点：

1. 队列中后面的元素可以比前面小，因为当前面的元素在滑出窗口的时候，后面小的元素可能是最大值。
2. 队列中的数组首尾存的下标的差值不能大于等于活动窗口大小，因为滑动窗口在那。

示例见书本

自己解题

你能想到的暴力解题，时间复杂度为O(nk)

参考解题

/**
 * 活动窗口的最大值
 *
 * @Author rex
 * 2018/9/17
 */
public class Solution {
    /**
     * 双端队列解题
     * @param num
     * @param size
     * @return
     */
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> maxInWindows = new ArrayList<>();
        if (num.length >= size && size >= 1) {
            // 双端队列
            LinkedList<Integer> index = new LinkedList<>();
            // 第一个滑动窗口，保持队首为最大值
            for (int i = 0; i < size; i++) {
                // 保证队列中后面的元素比前面小
                while (!index.isEmpty() && num[i] >= num[index.getLast()]) {
                    index.pollLast();
                }
                index.offer(i);
            }
            for (int i = size; i < num.length; i++) {
                maxInWindows.add(num[index.getFirst()]);
                while (!index.isEmpty() && num[i] >= num[index.getLast()]) {
                    index.pollLast();
                }
                // 如果队首不在滑动窗口内，则从队首移除
                if (!index.isEmpty() && index.getFirst() <= (i-size)) {
                    index.pollFirst();
                }
                index.offer(i);
            }
            // 最后一个滑动窗口
            maxInWindows.add(num[index.pollFirst()]);
        }
        return maxInWindows;
    }
}