滑动窗口最大值
滑动窗口最大值
描述
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例
输入: 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
题解
暴力破解
思路
遍历每个滑动窗口，在每个滑动窗口中获取最大值；
代码
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + k; j++)
max = Math.max(max, nums[j]);
output[i] = max;
}
return output;
}
复杂度分析
时间复杂度： 在nums数组中遍历获得滑动窗口O(N)，在滑动窗口中获取最大值的时间复杂度为O(k),
因为每一次遍历数组获取滑动窗口都需获取滑动窗口的最大值，
因此最终的时间复杂度为O(N*k);
空间复杂度：返回值所需O(N-l+1);
优先队列
思路
使用大顶堆来维护滑动窗口中的的数据，大顶堆的堆顶元素即为滑动窗口中最大值。
算法步骤：
- 准备：
- 源数据nums数组，长度为N
- 滑动窗口大小k
- 优先队列（大顶堆）priorityQueue，大小需为k
- 结果数组results，长度为N-k+1
- 初始化priorityQueue：由于滑动窗口是从nums的下标k-1开始遍历的,因此先
使用nums中[0,k-1]上的值来初始化priorityQueue;
nums[0,k-1]为第一个滑动窗口，因此results[0]为此时priorityQueue的最优先元素； - 遍历nums：从k到N遍历nums，下标为i,此时滑动窗口范围为nums[i-k+1,i],priorityQueue
的值为nums[i-k,i-1]； - 调整优先队列：将nums[i]添加到priorityQueue，nums[i-k],从priorityQueue移除，
保持priorityQueue的值与滑动窗口的值一致； - 添加滑动窗口最大值：优先队列的队首元素为滑动窗口此时的最大值，
results[i-k+1]=priorityQueue的队首元素；
代码
public class PriorityQueueSolution {
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
};
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (k > len || k < 1) {
return new int[0];
}
int[] result = new int[len - k + 1];
PriorityQueue<Integer> queue = new PriorityQueue<>(k, comparator);
//初始化优先队列
int i = 0;
while (i < k - 1) {
queue.add(nums[i]);
i++;
}
//从滑动窗口中获取最大值
for (int right = k - 1; right < len; right++) {
queue.add(nums[right]);
if (queue.size() > k) {
queue.remove(nums[right-k]);
}
result[right - k + 1] = queue.element();
}
return result;
}
}
复杂度分析
时间复杂度： 在nums数组中遍历获得滑动窗口O(N)，优先队列删除、添加元素的复杂度为O(logk),
获取优先队列的队首元素的时间复杂度为O(1),
因此最终的时间复杂度为O(N*logk);
空间复杂度：返回值所需O(N-l+1),优先队列为O(k),最终为O(N);
双端队列
思路
使用双端队列来存储滑动窗口在nums中对应的下标；
双端队列限制：
- 靠近尾部的队列元素的值需要比靠近队首的元素的值要大，
即当窗口滑动时，滑动窗口中增加的元素在nums的下标是从队尾添加的，
滑动窗口移除的元素在nums中的下标是从队首移除的； - 靠近尾部的队列元素的值作为下标在nums值需要比靠近队首的要小，
即当队列添加下标之前要从队列队尾去除这些下标（它们在nums中对应的值要比要添加
下标在nums中的要小）；
经过上述限制，队列的队首下标在nums中对应的值始终是队列的最大值，即为滑动窗口中的最大值；
代码
public class DequeSolution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (k > len || k < 1) {
return new int[0];
}
int[] result = new int[len - k + 1];
//用于存储在滑动窗口中有效的索引，且双端队列会从前向后维护一个降序的排列，
// 获取滑动窗口中的最大值，只需要获取双端队列的首值即可
Deque<Integer> indexDeque = new ArrayDeque<>(k);
for (int i = 0; i < len; i++) {
addAndRemove(nums, indexDeque, i, k);
if (i >= k - 1) {
result[i - k + 1] = nums[indexDeque.getFirst()];
}
}
return result;
}
private void addAndRemove(int[] nums, Deque<Integer> indexDeque, int index, int k) {
//如果indexDeque中的开始元素的索引在当前滑动窗口的范围之外删除
if (indexDeque != null && indexDeque.size() > 0 && (index - indexDeque.getFirst()) > k - 1) {
indexDeque.removeFirst();
}
//循环从indexDeque后部取出索引indexLast，与要添加的索引index，将它们在nums中的值比较，若值indexLast的值比较小，
// 则将indexLast从indexDeque删除，这样可以保证indexDeque中的索引在nums中的取值是降序排列，也能保证indexDeque中的
// 首个值是滑动窗口的最大值的索引
while (indexDeque != null && indexDeque.size() > 0 && nums[index] > nums[indexDeque.getLast()]) {
indexDeque.removeLast();
}
indexDeque.addLast(index);
}
}
复杂度分析
时间复杂度： 在nums数组中遍历获得滑动窗口O(N)，双端队列删除、获取队首元素的复杂度为O(1);添加元素的复杂度为O(1)~O(logk),
因此最终的时间复杂度为O(N)~O(log(k));
空间复杂度：返回值所需O(N-l+1),双端队列为O(k),最终为O(N);
动态规划
思路
构造left,right数组；
- 将nums按k的大小分成多段，最后一段可能不到k个元素；
- left数组中，left中按分段与nums对应，left分段中从左到右对应索引的值，是nums对应分段中对应索引及之前的索引的之中最大的一个值
- right数组中，right中按分段与nums对应，right分段中从右到左对应索引的值，是nums对应分段中对应索引及之前的索引的之中最大的一个值
- 因此获取一个滑动窗口的最大值，是max(滑动窗口最左边位置的索引在right数组中的值,滑动窗口最右边位置的索引在left数组中的值
代码
public class DynamicProgrammingSolution implements ISolution {
@Override
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (k > len || k < 1) {
return new int[0];
}
int[] left=new int[len];
int[] right=new int[len];
//构造left、right数组
for(int i=0;i<len;i++){
//left构造
if(i%k==0){
left[i]=nums[i];
}else{
left[i]=Math.max(left[i-1],nums[i]);
}
//right构造,从nums数组右边开始遍历
int index=len-i-1;
if(index==len-1||(index+1)%k==0){
right[index]=nums[index];
}else{
right[index]=Math.max(right[index+1],nums[index]);
}
}
//获取滑动窗口最大值数组
int[] result=new int[len-k+1];
for(int i=0;i<len-k+1;i++){
result[i]=Math.max(right[i],left[i+k-1]);
}
return result;
}
}
复杂度分析
时间复杂度： 构造left，rigt数组O(N),在nums数组中遍历获得滑动窗口O(N).
因此最终的时间复杂度为O(2N);
空间复杂度：返回值所需O(N-l+1),left,right数组分别为O(N),最终为O(3N);
