题解 | #滑动窗口的最大值#

【问题描述】

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

【解题思路】

• 维护一个和窗口大小相等的大顶堆，堆顶元素则为当前窗口最大值。
• 假设窗口大小为M，数组长度为N。窗口向右移动时，需要先在堆中删除离开窗口的元素，
• 并将新到达的元素添加到堆中，这两个操作的时间复杂度都为log2M，
• 因此算法的时间复杂度为O(log2M)，空间复杂度为O(M)

【代码示例】

public ArrayList<Integer> maxInWindows(int[] nums, int size) {
        ArrayList<Integer> ret = new ArrayList<>();

        if (size > nums.length || size < 1) {
            return ret;
        }

        // 建立大堆顶
        PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);

        // 控制滑动窗口输入元素
        for (int i = 0; i < size; i++) {
            heap.add(nums[i]);
        }
        // 取出窗口内的最大元素
        ret.add(heap.peek());
        // 移动滑动窗口
        for (int i = 0, j = i + size; j < nums.length; i++, j++) {
            heap.remove(nums[i]);
            heap.add(nums[j]);
            ret.add(heap.peek());
        }
        return ret;
    }