給定1個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。
例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那末1共存在6個(gè)滑動(dòng)窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)：
{[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：暴力
時(shí)間復(fù)雜度：
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> result = new ArrayList<Integer>();
int len = num.length;
if(size<=0 || size> len)
return result;
for(int i=0;i<len;i++){
int max = Integer.MIN_VALUE;
for(int k=0;k+i < len && k<size;k++){
max = max>num[i+k]?max:num[i+k];
}
result.add(max);
if(i+size==len)
break;
}
return result;
}
}方法2：利用隊(duì)列
隊(duì)列寄存滑動(dòng)窗口中較大元素的下標(biāo)
import java.util.ArrayList;
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> result = new ArrayList<>();
if (num == null) {
return result;
}
if (num.length < size || size < 1) {
return result;
}
LinkedList<Integer> indexDeque = new LinkedList<>();
for (int i = 0; i < size; i++) {
while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) {
indexDeque.removeLast();
}
indexDeque.addLast(i);
}
for (int i = size; i < num.length ; i++) {
result.add(num[indexDeque.getFirst()]);
while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) {
indexDeque.removeLast();
}
if (!indexDeque.isEmpty() && indexDeque.getFirst() <= (i - size)) {
indexDeque.removeFirst();
}
indexDeque.addLast(i);
}
result.add(num[indexDeque.getFirst()]);
return result;
}
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
