一、題目

給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在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 package algorithm7; 2 3 import java.util.ArrayList; 4 import java.util.LinkedList; 5 //使用雙端隊(duì)列 6 /* 7 對(duì)新來(lái)的元素k，將其與雙端隊(duì)列中的元素相比較 8 * 1）前面比k小的，直接移出隊(duì)列（因?yàn)椴辉倏赡艹蔀楹竺婊瑒?dòng)窗口的最大值了!）, 9 * 2）前面比k大的X，比較兩者下標(biāo)，判斷X是否已不在窗口之內(nèi)，不在了，直接移出隊(duì)列 10 * 隊(duì)列的第一個(gè)元素是滑動(dòng)窗口中的最大值*/ 11 public class MaxInWindows64 { 12 public static void main(String[] args) { 13 int[] num = {2,3,4,2,6,2,5}; 14 ArrayList<Integer> res = maxInWindows(num,3); 15 for(int i : res){ 16 System.out.print(i + " "); 17 } 18 } 19 public static ArrayList<Integer> maxInWindows(int [] num, int size){ 20 ArrayList<Integer> res = new ArrayList<>(); 21 if(size == 0 || size > num.length) 22 return res; 23 int begin; 24 LinkedList<Integer> q = new LinkedList<>(); 25 //先將前size-1個(gè)數(shù)中的符合條件的值 加入雙端隊(duì)列中 26 for(int i = 0; i < size - 1; i++){ 27 while(!q.isEmpty() && num[i] > num[q.getLast()]){ 28 q.removeLast(); 29 } 30 q.addLast(i); 31 } 32 for(int i = size-1; i < num.length; i++){ 33 while(!q.isEmpty() && num[i] > num[q.getLast()]){ 34 q.removeLast(); 35 } 36 q.addLast(i); 37 if(i-q.getFirst()+1 > size) 38 q.removeFirst(); 39 res.add(num[q.getFirst()]); 40 } 41 return res; 42 } 43 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/fankongkong/p/7462165.html

總結(jié)

以上是生活随笔為你收集整理的62、滑动窗口的最大值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。