双指针-滑动窗口的最大值-JZ64

96 阅读 0 评论 64 点赞

我是靠谱客的博主勤劳裙子，最近开发中收集的这篇文章主要介绍双指针-滑动窗口的最大值-JZ64，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度的时候，返回空

示例1

输入： [2,3,4,2,6,2,5,1],3
返回值： [4,4,6,6,6,5]

思路1：
最大堆保存滑动窗口数据，
时间复杂度：O(n*logk), 其中n为数组大小，k为窗口大小
offer(),remove()时间复杂度均为log(N)
空间复杂度：O(k)，k为窗口大小

代码1：最大堆

import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if (num == null || num.length < size || size <= 0) {
return res;
}
PriorityQueue<Integer> maxQueue = new PriorityQueue<>((o1, o2)->o2-o1);
int i = 0;
//初始化最大堆
while (i < size) {
maxQueue.offer(num[i]);
i++;
}
res.add(maxQueue.peek());
while (i < num.length) {
maxQueue.remove(num[i-size]);
maxQueue.offer(num[i]);
res.add(maxQueue.peek());
i++;
}
return res;
}
}

思路2：
双指针的思路：
快指针right 指向滑动窗口下一个要加入的位置
慢指针maxIndex指向滑动窗口内最大值
每次直接拿num[right] 和 num[maxIndex]进行比较，如果maxIndex正好是滑动窗口的第一个数字，代表右移的话正好最大值移除，需要特殊处理，重新遍历一下滑动窗口获取最大值
时间复杂度：O(n), 其中n为数组大小，k为窗口大小
基本可以认是为O(n)，最坏为O(n*k)
空间复杂度：O(k)，k为窗口大小

代码2

import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if (num == null || num.length < size || size <= 0) {
return res;
}
//maxIndex表示滑动窗口内最大值下标
int maxIndex = 0;
for (int i = 1; i < size; i++){
if (num[i] >= num[maxIndex]) {
maxIndex = i;
}
}
res.add(num[maxIndex]);
// right表示下一个加入滑动窗口的值
int right = size;
while (right < num.length) {
if (num[right] >= num[maxIndex]) {
maxIndex = right;
} else {
//滑动窗口最大值为第一个位置的情况 右移后最大值需要重新计算
if (right - size == maxIndex) {
int tempMaxIndex = right - size + 1;
for (int i = tempMaxIndex + 1; i <= right; i++) {
if (num[i] >= num[tempMaxIndex]) {
tempMaxIndex = i;
}
}
maxIndex = tempMaxIndex;
}
}
right++;
res.add(num[maxIndex]);
}
return res;
}
}