2
#yyds干货盘点# 面试必刷TOP101：滑动窗口的最大值
source link: https://blog.51cto.com/u_15488507/5666567
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：滑动窗口的最大值
精选 原创1.简述：
描述
给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{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]
示例2
[9,10,9,-7,-3,8,2,-6],5
[10,10,9,8]
示例3
[1,2,3,4],3
[3,4]
2.代码实现：
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<Integer>();
//窗口大于数组长度的时候，返回空
if(size <= num.length && size != 0){
//双向队列
ArrayDeque <Integer> dq = new ArrayDeque<Integer>();
//先遍历一个窗口
for(int i = 0; i < size; i++){
//去掉比自己先进队列的小于自己的值
while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
dq.pollLast();
dq.add(i);
}
//遍历后续数组元素
for(int i = size; i < num.length; i++){
//取窗口内的最大值
res.add(num[dq.peekFirst()]);
while(!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
//弹出窗口移走后的值
dq.pollFirst();
//加入新的值前，去掉比自己先进队列的小于自己的值
while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
dq.pollLast();
dq.add(i);
}
res.add(num[dq.pollFirst()]);
}
return res;
}
}
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<Integer>();
//窗口大于数组长度的时候，返回空
if(size <= num.length && size != 0){
//双向队列
ArrayDeque <Integer> dq = new ArrayDeque<Integer>();
//先遍历一个窗口
for(int i = 0; i < size; i++){
//去掉比自己先进队列的小于自己的值
while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
dq.pollLast();
dq.add(i);
}
//遍历后续数组元素
for(int i = size; i < num.length; i++){
//取窗口内的最大值
res.add(num[dq.peekFirst()]);
while(!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
//弹出窗口移走后的值
dq.pollFirst();
//加入新的值前，去掉比自己先进队列的小于自己的值
while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
dq.pollLast();
dq.add(i);
}
res.add(num[dq.pollFirst()]);
}
return res;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK