题目概览给你一个整数数组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 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7示例 2输入nums [1], k 1输出[1]提示1 nums.length 105-104 nums[i] 1041 k nums.length来源239. 滑动窗口最大值 - 力扣LeetCode解题分析方法一优先队列优先队列PriorityQueue即堆会保证堆顶的元素一定是最大值因此我们只需要把滑动窗口里的元素加进去就可以得到最大值。当滑动窗口移动时先将右侧元素入堆因为堆无法指定元素出堆我们可以定义进入堆的元素为 nums 和 索引 的映射当堆顶的元素 索引 小于 i - k 即 元素不属于当前滑动窗口 时移除堆顶元素否则记录当前元素。时间复杂度O(n*logn)空间复杂度O(n)class Solution { public int[] maxSlidingWindow(int[] nums, int k) { PriorityQueueint[] pq new PriorityQueueint[]( new Comparatorint[]() { public int compare(int[] a, int[] b) { return a[0] b[0] ? b[1] - a[1] : b[0] - a[0]; } } ); int len nums.length; int[] result new int[len - k 1]; for (int i 0; i k; i) { pq.offer(new int[]{nums[i], i}); } result[0] pq.peek()[0]; for (int i k; i len; i) { pq.offer(new int[]{nums[i], i}); while(pq.peek()[1] i - k) { pq.poll(); } result[i - k 1] pq.peek()[0]; } return result; } }方法二单调队列定义当前索引为 i当 nums[ i ] nums[ i - 1 ] 时nums[ i - 1 ] 已经不可能是后面的最大值了那么我们可以忽略它当 nums[ i ] nums[ i - 1 ] 时nums[ i ] 可能是后面的最大值我们需要存储它。我们可以定义 j 1 j k 定义一个队列来存储数据当 nums[ i ] nums[ i - j ] 时就往队列尾部移除 nums[ i - j ]当 nums[ i ] nums[ i - j ] 时就往队列尾部添加 nums[ i - j ]。这样的队列里面的元素一定是严格递减那么队列头部的元素一定是最大值但是头部的元素不一定是滑动模块里的元素因此还要做一步操作当队列头部的索引 i - k 时移除队列头部的元素。时间复杂度O(n)空间复杂度O(k)class Solution { public int[] maxSlidingWindow(int[] nums, int k) { DequeInteger dp new LinkedList(); int len nums.length; int[] result new int[len - k 1]; for (int i 0; i k; i) { while (!dp.isEmpty() nums[dp.peekLast()] nums[i]) { dp.pollLast(); } dp.offerLast(i); } result[0] nums[dp.peekFirst()]; for (int i k; i len; i) { while (!dp.isEmpty() nums[dp.peekLast()] nums[i]) { dp.pollLast(); } dp.offerLast(i); while (dp.peekFirst() i - k) { dp.pollFirst(); } result[i - k 1] nums[dp.peekFirst()]; } return result; } }