刷题分享：LeetCode239.滑动窗口最大值【优先队列&单调队列】

题目对应LeetCode239. 滑动窗口最大值

1. 题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例：

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

解释：
滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例 2：

输入：nums = [1], k = 1
输出：[1]

2. 题解

2.1 优先队列

思路

使用优先队列（堆）保存遍历过得数，以大顶堆保存，每次取出堆顶元素即为遍历过得最大元素，当堆顶元素下边与当前遍历下标值的距离超过窗口大小时，表示该元素不在窗口内，弹出该堆顶元素。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 存储的是索引，值的大根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> nums[b]-nums[a]);
        int[] res = new int[nums.length-k+1];
        for (int i=0; i<nums.length; i++) {
            if (i < k-1) {
                pq.offer(i);
                continue;
            }
            pq.offer(i);
            // 移除超出窗口的索引
            while (!pq.isEmpty() && pq.peek() < i-k+1) {
                pq.poll();
            }
            res[i-k+1] = nums[pq.peek()];
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(nlog(n))。优先队列添加元素的复杂度为O(log(n))。
空间复杂度：O(n)

2.2 单调队列

思路

假设下标i<j，说明i在j左侧，且有nums[i]<=nums[j]，则在窗口向右滑动过程中nums[i]一定不可能是窗口的最大值，因此我们可以将nums[i]移除掉。

我们使用双端队列来保存遍历到的元素，保证队列内的元素保持单调递减，在窗口向右滑动过程中，将新元素插入到队列尾部，在此之前需要不断取出队尾元素并判断新元素是否大于等于队尾元素，如果是则弹出队尾元素，直到队列为空或者队尾元素大于新元素，才能始终保证队列单调递减。由于队列是单调递减的，因此队首元素为遍历元素的最大值，但需要判断队首元素下标是否在窗口内，如果不在窗口内则需要弹出队首元素。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n-k+1];
        for (int i=0; i<n; i++) {
            // 保证队列单调递减
            while (!deque.isEmpty() && nums[deque.getLast()]<=nums[i]) {
                deque.pollLast();
            }
            // 保证队首元素在窗口内
            while (!deque.isEmpty() && deque.getFirst()<i-k+1) {
                deque.pollFirst();
            }
            deque.offerLast(i);
            // System.out.println(deque);
            if (i >= k-1) {
                res[i-k+1] = nums[deque.getFirst()];
            }
        }
        return res;
    }
}