网站标题的设置方法,和田地区建设局网站,google学术搜索,做黑网站赚钱一、题目 给定一个数组和滑动窗口的大小#xff0c;找出所有滑动窗口里数值的最大值。例如#xff0c;如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3#xff0c;那么一共存在6个滑动窗口#xff0c;他们的最大值分别为{4,4,6,6,6,5}#xff1b; 针对数组{2,3,4,2,6,2,5…一、题目 给定一个数组和滑动窗口的大小找出所有滑动窗口里数值的最大值。例如如果输入数组{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 package algorithm7;2 3 import java.util.ArrayList;4 import java.util.LinkedList;5 //使用双端队列6 /*7 对新来的元素k将其与双端队列中的元素相比较8 * 1前面比k小的直接移出队列因为不再可能成为后面滑动窗口的最大值了!,9 * 2前面比k大的X比较两者下标判断X是否已不在窗口之内不在了直接移出队列
10 * 队列的第一个元素是滑动窗口中的最大值*/
11 public class MaxInWindows64 {
12 public static void main(String[] args) {
13 int[] num {2,3,4,2,6,2,5};
14 ArrayListInteger res maxInWindows(num,3);
15 for(int i : res){
16 System.out.print(i );
17 }
18 }
19 public static ArrayListInteger maxInWindows(int [] num, int size){
20 ArrayListInteger res new ArrayList();
21 if(size 0 || size num.length)
22 return res;
23 int begin;
24 LinkedListInteger q new LinkedList();
25 //先将前size-1个数中的符合条件的值 加入双端队列中
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 } 转载于:https://www.cnblogs.com/fankongkong/p/7462165.html
