給定1個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。
例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那末1共存在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：暴力
時間復雜度：
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：利用隊列
隊列寄存滑動窗口中較大元素的下標
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網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
