239.滑动窗口最大值

给你一个整数数组 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]

提示：

• $1\le nums.length\le 10^5$
• $-10^4\le nums[i]\le 10^4$
• $1\le k\le nums.length$

解法一(优先队列)

思路分析：

1. 对于求滑动窗口的最大值，可以使用优先队列，其中的大根堆可以帮助我们实时维护一系列元素中的最大值
2. 首先将nums数组的前k个元素放入优先队列中，当向右移动窗口时，将新元素放入优先队列中，此时堆顶的元素是堆中所有元素的最大值，但是这个元素可能不在滑动窗口中
3. 当最大值不在滑动窗口中时，需要判断该值在数组nums的位置在滑动窗口左边界的左侧，所以在继续移动窗口时，若最大值不在滑动窗口中，则永久移除优先队列
4. 不断移除堆顶的元素，直到堆顶元素在滑动窗口中，此时堆顶元素为滑动窗口中的最大值
5. 为了方便判断堆顶元素是否在滑动窗口中，可以使用优先队列存储二元组(num, index)，index为元素num在数组中的下标

实现代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
		int n = nums.length;	// 数组nums长度
		// 创建 优先队列 并设置堆中元素比较方式
		PriorityQueue<int[]> pq = new PriorityQueue<>(
				(o1, o2) -> o1[0] != o2[0]? o2[0]-o1[0] : o2[1] - o1[1]
		);
		// 先将第一组滑动窗口 添加到优先队列中
		for (int i = 0; i < k; ++ i) {
			pq.offer(new int[]{nums[i], i});
		}
		int[] ans = new int[n-k+1];		// 返回最大值结果数组 且一共有n-k+1个窗口
        ans[0] = pq.peek()[0];
		// 移动滑动窗口 进行遍历
		for (int i = k; i < n; ++ i) {
			pq.offer(new int[]{nums[i], i});	// 将右窗口元素加入到优先队列中
			while (pq.peek()[1] <= i-k) {	// 将不在窗口内的最大值移除
				pq.poll();
			}
			ans[i-k+1] = pq.peek()[0];	// 记录窗口内的最大值
		}
		return ans;
    }
}

提交结果：

解答成功:
执行耗时:90 ms,击败了11.01% 的Java用户
内存消耗:56.2 MB,击败了96.20% 的Java用户

复杂度分析：

• 时间复杂度：$O(nlo{g}_{}n)$，维护优先队列中堆顶最大值时间复杂度为$O(lo{g}_{}n)$，同时需要遍历每个窗口的时间复杂度为$O(n-k+1)$，所以综合得时间复杂度为$O(nlo{g}_{}n)$
• 空间复杂度：$O(n)$，维护优先队列，保存数组中的元素

解法二(单调队列)

思路分析：

1. 根据解法一进行优化，可以使用一个队列来维护没有被移除的数组元素的下标，并且这些下标对应的元素是严格单调递减的
2. 当滑动窗口向右移动时，需要将一个新的元素放入队列中，此时需要新元素与队尾的元素比较，即如果队尾元素小于新元素，则永久移除，保证新的元素小于队尾的元素
3. 且此时队首元素就是滑动窗口中的最大值，但是与解法一中一样，需要判断最大值是否在滑动窗口中，若不在则弹出，并继续进行判断
4. 因为需要对队首和队尾的元素进行操作，所以使用双端队列来实现单调队列

实现代码如下：

class Solution {
	public int[] maxSlidingWindow(int[] nums, int k) {
		int n = nums.length;	// 数组nums长度
		Deque<Integer> deque = new ArrayDeque<>();	// 双端队列 用作维护单调队列
		int[] ans = new int[n-k+1];		// 返回结果数组 且计算得滑动窗口数量为n-k+1
		for (int i = 0; i < k; ++i) {	// 将第一组滑动窗口元素加入队列中
			// 将小于新元素的队尾元素 移除队列
			while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
				deque.pollLast();
			}
			deque.offerLast(i);	// 将新元素添加到队尾
		}
		ans[0] = nums[deque.peekFirst()];
		for (int i = k; i < n; ++i) {
			// 将队尾小于新元素的数组元素 移除
			while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()])
				deque.pollLast();
			deque.offerLast(i);		// 将新元素添加到队尾
			// 将队首 不在滑动窗口内的最大值移除
			while (!deque.isEmpty() && deque.peekFirst() <= i-k)
				deque.pollFirst();
			ans[i-k+1] = nums[deque.peekFirst()];
		}
		return ans;
	}
}

提交结果如下：

解答成功:
执行耗时:30 ms,击败了60.89% 的Java用户
内存消耗:63.2 MB,击败了5.02% 的Java用户

复杂度分析：

• 时间复杂度：$O(n)$，对每个元素遍历一次，且每个元素进队和出队一次
• 空间复杂度：$O(n)$，使用双端队列维护单调队列