【题目】给出一个整形数组，例如arr = {5,4,3,5,6,7,6}，窗口大小为w=3，窗口每次向右移动一位，输出每个窗口中最大值组成的数组。

package string;

import com.google.common.collect.Lists;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Random;

/**
 * Created by cqs on 2018/3/17.
 */
public class MaxArray {

    private static Random random = new Random();


    public static void main(String[] args) {
//        int[] a = {4, 3, 5, 4, 3, 3, 6, 7};
        Integer[] a = {5, 4, 3, 5, 6, 7, 6};
        a = randArr(10);
        int windows = 3;
        Integer[] result = getMaxArray(a, windows);
        System.out.println(Lists.newArrayList(result));

    }

    /**
     * 使用双端队列存储数组索引
     * 队首是当前最大的值
     * <p>
     * <p>
     * 遍历数组的时候 当下一个数的值小于队尾时候添加到队列尾部
     * 当下一个数X大于等于队尾时 删除队尾元素  并继续和新的队尾比较 直到不大于队尾元素或者队列为空
     * 然后添加X的索引到队列尾部
     * <p>
     * 将队列首部元素（索引）对应数组的值存储到结果数组中
     * <p>
     * 队列最多windows个元素 当队列超过windows个元素时 队首元素过期了 （窗口已经划过了） 需要删除队首元素
     */
    private static Integer[] getMaxArray(Integer[] a, int windows) {
        if (a == null || a.length < windows) return null;
        Deque<Integer> queue = new LinkedList<>();
        //处理第1个元素 至第windows -1个元素
        queue.add(0);
        for (int i = 1; i < windows - 1; i++) {
            int fIndex = queue.getFirst();
            if (a[i] > a[fIndex]) {
                queue.removeFirst();
                queue.addFirst(i);
            }
        }
        //从第windows个元素开始 每次求出一个窗口最大值
        Integer[] result = new Integer[a.length - windows + 1];
        for (int i = windows - 1; i < a.length; i++) {
            //a[i]大于等于队尾的话 删除队尾元素 直到队尾元素大于a[i] 或者队列为空
            while (queue.size() > 0 && a[queue.getFirst()] <= a[i]) {
                queue.removeLast();
            }
            //队尾添加
            queue.addLast(i);
            int fIndex = queue.getFirst();
            result[i - windows + 1] = a[fIndex];
            if (i - windows + 1 >= fIndex) { //本轮中窗口划过队首元素
                queue.removeFirst();
            }
        }
        return result;
    }

    private static Integer[] randArr(int size) {
        Integer[] as = new Integer[size];
        for (int i = 0; i < size; i++) {
            as[i] = random.nextInt(100 * size);
        }
        System.out.println(Lists.newArrayList(as));
        return as;
    }
}