【题目】
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右滑动一个位置。
例如,数组为[4,3,5,4,3,3,6,7],窗口大小为3时:
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7
【要求】
时间复杂度为O(n)
附上源码
package pers.mao.stackAndQueue.demo_07;
import java.util.LinkedList;
/**
* @author Mao Qingbo
* @date 2020-10-26
*/
public class Window {
/**
*
* @param arr 输入的整型数组
* @param w 窗口长度
* @return res[i]表示每一种窗口状态下的最大值
*/
public int [] getMaxWindow(int [] arr,int w){
if(arr == null || w < 1 || arr.length < w){//s非法输入
return null;
}
LinkedList<Integer> qmax = new LinkedList<Integer>();//双端队列qmax,qmax中存放arr中的下标
int index = 0;//res的下标
int [] res = new int [arr.length-w+1];
for(int i = 0; i < arr.length; i++){
while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
qmax.pollLast();
}
qmax.addLast(i);
if(qmax.peekLast() == i -w){//保证队头不过期
qmax.pollFirst();
}
if(i >= w - 1){
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
}
网友评论