基本的解决方案是生成所有大小为k的连续子数组并循环遍历它们以找出当前子数组中的最大值。考虑到，对于每个点，我们基本上都是取下一个
'k'元素，然后我们遍历那些 k 个元素，因此该算法的最坏时间复杂度将是
O(n*k)。
package Arrays;import java.util.Scanner;public class slidingWindowMax { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int [] arr = new int[scn.nextInt()]; for(int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } int windowSize = scn.nextInt(); solve(arr, windowSize); } public static void solve(int[] arr, int k) { // starting the outer loop from k and running it until, // current pointer is EQUAL to arr.length for(int i = k; i <= arr.length; i++) { int max = Integer.MIN_VALUE; // this loop considers subarrays of size k ending at i-1 for(int j = i-k; j<i; j++) { max = Math.max(max, arr[j]); } System.out.println(max); } }}稍微有效的方法：
通过使用Segment 树，我们肯定可以减少为每个子数组寻找最大值所花费的时间。
我们可以为给定的数组实现一个段树，我们可以通过范围查询[i, i+k-1]获取每个子数组的最大值。
段树中的节点总数：
构建段树的最坏时间复杂度为O(n)，因为我们知道，
(i) 段树的叶节点包含数组的所有元素。
(ii) 最后一层的节点数是所有上一层的节点数。
在数学上，
考虑数组的长度为 n，因此，线段树的叶节点将为 n。
因此，所有上层的节点数将为 n-1。
长度为 n 的数组的段树上的总节点数为：
Tn = leaf nodes + nodes on upper levels = n + n-1 = 2n+1
复杂性分析
我们的线段树的构建只涉及对每个节点的计算一次，因此构建线段树的最坏时间复杂度将是 O(2n+1) 即O(n)。
每个子数组的范围查询的结果将在O(logk) 中计算。
将对所有大小为 k 的“n-k+1”个子数组进行查询计算。
因此该算法的整体时间复杂度为 O((n-k+1)*logk) 即O(nlogk)。
package Arrays;import java.util.Scanner;public class slidingWindowMax { static int[] sarr; public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } int windowSize = scn.nextInt(); int height = (int)Math.ceil((Math.log(arr.length) / Math.log(2))); sarr = new int[1<<height -1]; construct(0, 0, arr.length-1, arr); solve(arr, windowSize); } public static void solve(int[] arr, int k) { for (int i = 0; i <= arr.length - k; i++) { System.out.println(query(0, i, i + k - 1, 0, arr.length - 1)); } } public static int construct(int idx, int start, int end, int[] arr) { if (start == end) { sarr[idx] = arr[end]; return sarr[idx]; } int mid = (start + end) / 2; int left = construct(2 * idx + 1, start, mid, arr); int right = construct(2 * idx + 2, mid + 1, end, arr); sarr[idx] = Math.max(left, right); return sarr[idx]; } public static int query(int idx, int queryStart, int QueryEnd, int start, int end) { if (start > QueryEnd || end < queryStart) { return Integer.MIN_VALUE; } else if (start >= queryStart && end <= QueryEnd) { return sarr[idx]; } else { int mid = (start + end) / 2; int left = query(2 * idx + 1, queryStart, QueryEnd, start, mid); int right = query(2 * idx + 2, queryStart, QueryEnd, mid + 1, end); return Math.max(left, right); } }}最有效的方法：
在这种方法中，我们使用Deque帮助我们找到O(n) 中的滑动窗口最大值。
Deque基本上是一个队列，其是在两个两个排队和deque，即，可以添加或删除元素或者从前面或后面的端部开放。
我们实际解决问题的方法是：
我们以相反的顺序保留子数组的 k 个元素，我们不需要保留所有的 k 个元素，尽管我们稍后会在代码中看到。
为前 k 个元素生成 Deque，保持它们以相反的顺序排序，以便最大元素位于最前面。
如果 Deque 为空，则直接添加元素，否则检查传入元素是否大于最后一个元素，如果是，则继续从最后一个元素弹出元素，直到剩余 Deque 的最后一个元素大于传入元素。
我们还需要删除属于不同子数组的元素。即 Deque 中的索引必须在[i, i+k]范围内。
一个元素只会在两种情况下被删除：
（i）如果即将到来的元素大于后部 元素，如果它，它将继续弹出元素，直到剩余出队的后部出现更大的元素，因为我们需要保持数组以相反的顺序排序。
(ii) 如果元素属于任何其他子数组，则保留它没有意义。
package org.arpit.java2blog;import java.util.linkedList;import java.util.Scanner;public class SlidingWindowMax { static int[] sarr; public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } System.out.print("arr[]: {"); for (int i = 0; i < arr.length; i++) { System.out.print(" "+arr[i]); } System.out.println(" }"); int windowSize = scn.nextInt(); solveEfficient(arr, windowSize); } public static void solveEfficient(int[] arr, int k) { linkedList<Integer> deque = new linkedList<>(); for (int i = 0; i < arr.length; i++) { while (!deque.isEmpty() && arr[deque.getLast()] <= arr[i]) { deque.removeLast(); } while (!deque.isEmpty() && deque.getFirst() <= i - k) { deque.removeFirst(); } deque.addLast(i); if(i >= k-1) { System.out.print(" "+arr[deque.getFirst()]); } } }}当你运行上面的程序时，你会得到以下输出：
82 6 -1 2 4 1 -6 5arr[]: { 2 6 -1 2 4 1 -6 5 }36 6 4 4 4 5
