栈和队列--生成窗口最大值数组

题目：

　　有一个整型数组arr和一个大小为w的窗口从数组最左边滑到最右边，窗口每次向右边滑一个位置

　　例如：数组为【4，3，5，4，3，3，6，7】，窗口大小为三时

　　如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值，要求时间复杂度为O（N）

　　实现一个函数：

　　　　输入：整型数组arr，窗口大小为w

　　　　输出：一个长度为n-w+1的数组，里面每一个元素表示一种窗口状态下的最大值

　　以上述例子为例，得到结果【5，5，5，4，6，7】

思路：通过创建一个双端队列，来存取数组arr的下标，假设遍历到数组arr[i]，队列放入规则如下：

　　如果队列为空，直接把下标i放入到队列中，放入过程结束；

　　如果队列不为空，取出当前队列队尾存放的下标，假设为j

　　　　如果arr[j] > arr[i] ,直接把下标i放进队列队尾，放入过程结束

　　　　如果arr[j] <= arr[i]，把j从队列弹出，重复上述规则 

代码实现如下：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class ListMaxWindow {
    public static void main(String[] args){
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.addLast(7);
        list.addFirst(8);
        System.out.println("list集合元素为：" + list);
        System.out.println("peekFirst:"+list.peekFirst());
        System.out.println("list集合元素为：" + list);
        System.out.println("peekLast:"+list.peekLast());
        System.out.println("list集合元素为：" + list);
        System.out.println("pollLast:"+list.pollLast());
        System.out.println("list集合元素为：" + list);
        System.out.println("pollFist:"+list.pollFirst());
        System.out.println("list集合元素为：" + list);


//        LinkedList<Integer> list1 = new LinkedList<>();
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//
//        while (n>0){
//            int value = scanner.nextInt();
//            list1.add(value);
//
//            n--;
//        }
//        int[] arr = new int[list1.size()];
//        for(int i = 0 ;i<arr.length;i++){
//            arr[i] = list1.get(i);
//        }
        int[] arr1 = {4, 3, 5, 4, 3, 3, 6, 7};
        int[] arr2;
        System.out.println(Arrays.toString(arr1));
        arr2 = getMaxWindow(arr1,3);
        for(int i = 0;i< arr2.length;i++){
            System.out.print(arr2[i] + " ");
        }
        System.out.println(Arrays.toString(arr2));





    }
    public static int[] getMaxWindow(int[] arr,int w){
        if(arr == null && w < 1 || arr.length < w){
            return null;
        }
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for(int i = 0;i < arr.length;i++){
            while (!qmax.isEmpty() && arr[qmax.peekLast()] < arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if(qmax.peekFirst() == i - w){
                qmax.pollFirst();
            }
            if(i >= w -1){
                res[index++] = arr[qmax.peekFirst()];
            }
        }

        return res;
    }
}

运行结果如下：