整型数组arr, 滑动窗口大小w, 窗口从左向右滑动，依次输出窗口内最大值
如数组为[3,5,6,2,3,4]， 滑动窗口大小：2
则输出[5,5,6,3,4]
public class MaxArray { public static void main(String[] args){ int[] arr = {6,6,8,5,9,3,3,6,7}; int[] output = max_way(arr, 3); for(int i=0; i< output.length; i++){ System.out.print(arr[output[i]] + ","); } } public static int[] max_way(int[] arr, int num){ //排查条件之外的情况 if(arr ==null || num<1 ||arr.length<num){ return arr; } //初始化需要返回的数组 int[] res = new int[arr.length - num +1]; //新建一个双端队列，用于存放最大值，注：始终保持队首在滑动框内为最大值 LinkedList<Integer> max_value = new LinkedList<Integer>(); int index = 0; for(int i=0; i<arr.length; i++){ while(!max_value.isEmpty() && arr[max_value.peekLast()]<=arr[i]){ max_value.pollLast(); } max_value.addLast(i); if(max_value.peekFirst() == i-num){ max_value.pollFirst(); } if(i>=num-1){ res[index++] = max_value.peekFirst(); } } return res; } }
