【題目】給出一個(gè)整形數(shù)組立宜，例如arr = {5,4,3,5,6,7,6}站叼，窗口大小為w=3充易，窗口每次向右移動(dòng)一位，輸出每個(gè)窗口中最大值組成的數(shù)組裁着。

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));

    }

    /**
     * 使用雙端隊(duì)列存儲(chǔ)數(shù)組索引
     * 隊(duì)首是當(dāng)前最大的值
     * <p>
     * <p>
     * 遍歷數(shù)組的時(shí)候 當(dāng)下一個(gè)數(shù)的值小于隊(duì)尾時(shí)候添加到隊(duì)列尾部
     * 當(dāng)下一個(gè)數(shù)X大于等于隊(duì)尾時(shí) 刪除隊(duì)尾元素  并繼續(xù)和新的隊(duì)尾比較 直到不大于隊(duì)尾元素或者隊(duì)列為空
     * 然后添加X(jué)的索引到隊(duì)列尾部
     * <p>
     * 將隊(duì)列首部元素（索引）對(duì)應(yīng)數(shù)組的值存儲(chǔ)到結(jié)果數(shù)組中
     * <p>
     * 隊(duì)列最多windows個(gè)元素 當(dāng)隊(duì)列超過(guò)windows個(gè)元素時(shí) 隊(duì)首元素過(guò)期了 （窗口已經(jīng)劃過(guò)了） 需要?jiǎng)h除隊(duì)首元素
     */
    private static Integer[] getMaxArray(Integer[] a, int windows) {
        if (a == null || a.length < windows) return null;
        Deque<Integer> queue = new LinkedList<>();
        //處理第1個(gè)元素 至第windows -1個(gè)元素
        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個(gè)元素開始 每次求出一個(gè)窗口最大值
        Integer[] result = new Integer[a.length - windows + 1];
        for (int i = windows - 1; i < a.length; i++) {
            //a[i]大于等于隊(duì)尾的話 刪除隊(duì)尾元素 直到隊(duì)尾元素大于a[i] 或者隊(duì)列為空
            while (queue.size() > 0 && a[queue.getFirst()] <= a[i]) {
                queue.removeLast();
            }
            //隊(duì)尾添加
            queue.addLast(i);
            int fIndex = queue.getFirst();
            result[i - windows + 1] = a[fIndex];
            if (i - windows + 1 >= fIndex) { //本輪中窗口劃過(guò)隊(duì)首元素
                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;
    }
}