给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值
https://leetcode-cn.com/problems/sliding-window-maximum/
示例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]
示例3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
示例4：
输入：nums = [9,11], k = 2
输出：[11]
示例 5：
输入：nums = [4,-2], k = 2
输出：[4]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
Java解法
思路：
题目内容比较好理解，就是滑动数组在滚动时返回每次滚动窗口内的最大值
初步设想：开始滚动时，维护当前窗口大小的一个数组，有序记录最大值，在滚动时对移除值及移入值进行一个大小维护替换
- 大小维护：对有序 数组二分查找更新
- 设想更新：对当前窗口的大小数据构建一个大堆维护，当最大值移除时
设想2：找到当前滑动窗口最大值，在滚动超出当前滑动窗口之前，最大值都不会变（在没有移入更大值之前）
在移除当前窗口最大值时，重新查找最大值
能够完成但效率低，超时
public static int[] maxSlidingWindow(int[] nums, int k) { //从0开始移动 int maxIndex = findMaxIndex(nums, 0, k); int length = nums.length; int moveStep = length - k+1; int[] maxNums = new int[moveStep]; maxNums[0] = nums[maxIndex]; for (int i = 1; i < moveStep; i++) { //移入的值为 i+k-1 maxIndex = nums[maxIndex]>nums[i+k-1]?maxIndex:i+k-1; if (i>maxIndex) { maxIndex = findMaxIndex(nums,i,k+i); } maxNums[i] = nums[maxIndex]; } return maxNums; } public static int findMaxIndex(int[] nums, int start, int end) { int max = start; for (int i = start+1; i < end; i++) { max = nums[i]>=nums[max]? i:max;//因为向右移动，所有相等时取index更大的值可以减少计算步骤 } return max; }参考官方解：单调队列
- 算是对我的方法的优化吧，元素 n-1与n 如果nums[n-1]<nums[n]，那n-1在窗口中时，最大值一定不会为它
- 按照这个性质来进行队列的维护
package sj.shimmer.algorithm.m4_2021;
import java.util.Deque;
import java.util.LinkedList;
import sj.shimmer.algorithm.Utils;
/**
* Created by SJ on 2021/4/23.
*/
class D86 {
public static void main(String[] args) {
Utils.logArray(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3));
Utils.logArray(maxSlidingWindow(new int[]{1},1));
Utils.logArray(maxSlidingWindow(new int[]{1,-1},1));
Utils.logArray(maxSlidingWindow(new int[]{9,11},2));
Utils.logArray(maxSlidingWindow(new int[]{4,-2},2));
}
public static int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
//双端队列存储前k个元素的可永久移除的数据，严格的单调递减
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
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.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
官方解
-
优先队列
我设想的解决方案，这里用大根堆来解决了维护问题
-
单调队列
参考方案：见上
-
分块 + 预处理
数学知识，