双端队列：双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2：简单来说就是前端和尾端都可以删除或者插入

只便利了一次 减去旧值得 加上新值 得到新的和

只要是子串 子数组 就可以使用此算法

重点是走了一个值。再来了一个值 查找子串

要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n2)的算法，但我们可以做得更好。通过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。

采取了滑动窗口技术(思路)，消除或者减少【求最大值还是需要少量的循环】内部循环

package com.cdfive.learn2018.algorithm;

/**
 * 求数组array长度为k的子数组的最大和
 *
 * 算法1-cal
 * 遍历所有子数组，求和并比较
 * 嵌套循环 O(n*k)
 *
 * 算法2-calByLeapWinow
 * 窗口向右滑动，减去失效值加上最新值
 * 单层循环 O(n)
 *
 * input:  array=[1,2,3,4] k=2
 * output: 7 // 3+4
 *
 * input:  array=[-1,4,7,-3,8,5,-2,6] k=3
 * output: 12 // 7-3+8
 *
 * @author cdfive
 * @date 2018-12-02
 */
public class SimpleLeapWindow1 {

    public static void main(String[] args) {
        cal(new int[]{1, 2, 3, 4}, 2);
        cal(new int[]{-1,4,7,-3,8,5,-2,6}, 3);

        System.out.println("-------------");

        calByLeapWinow(new int[]{1, 2, 3, 4}, 2);
        calByLeapWinow(new int[]{-1,4,7,-3,8,5,-2,6}, 3);
    }

    /**
     * 遍历所有子数组，求和并比较
     * 嵌套循环 O(n*k)
     */
    public static void cal(int[] array, int k) {
        if (array.length == 0 || k <= 0 || k > array.length) {// 非法参数不处理
            return;
        }

        int index = 0;// 记录最大子数组第1个元素的索引，目前是0
        int maxSum = 0;// 记录最大子数组和，目前是从左开始第1个子数组
        for (int i = 0; i < k; i++) {
            maxSum += array[i];
        }

        for (int i = 1; i <= array.length - k; i++) {// 遍历所有子数组，求和并比较
            int curSum = 0;
            for (int j=0; j < k; j++) {// 计算当前子数组和
                curSum += array[i + j];
            }
            if (curSum > maxSum) {// 如果大于最大和，则记录
                maxSum = curSum;
                index = i;
            }
        }

        /**打印结果*/
        System.out.print(maxSum + " // ");// 打印最大和
        System.out.print(array[index]);// 先打印第1个值
        for (int i = 1; i < k; i++) {
            int value = array[i + index];
            System.out.print(value >= 0 ? ("+" + value) : value);// 非负数前面打印+号
        }
        System.out.println();
    }

    /**
     * 窗口向右滑动，通过减失效值加最新值求和并比较
     * 单层循环 O(n)
     */
    public static void calByLeapWinow(int[] array, int k) {
        if (array.length == 0 || k <= 0 || k > array.length) {// 非法参数不处理
            return;
        }

        int index = 0;// 记录最大子数组第1个元素的索引，目前是0
        int maxSum = 0;// 记录最大子数组和，目前是从左开始第1个子数组
        for (int i = 0; i < k; i++) {
            maxSum += array[i];
        }

        int curWindowSum = maxSum;
        for (int i = 1; i <= array.length - k; i++) {// 从下个元素开始，即窗口向右滑动
            curWindowSum = curWindowSum - array[i - 1] + array[k + i - 1];// 减去失效值，加上最新值
            if (curWindowSum > maxSum) {// 如果大于最大和，则记录
                maxSum = curWindowSum;
                index = i;
            }
        }

        /**打印结果*/
        System.out.print(maxSum + " // ");// 打印最大和
        System.out.print(array[index]);// 先打印第1个值
        for (int i = 1; i < k; i++) {
            int value = array[i + index];
            System.out.print(value >= 0 ? ("+" + value) : value);// 非负数前面打印+号
        }
        System.out.println();
    }
}

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。 以数组为[4,3,5,4,3,3,6,7] 那么输出5 5 5 4 6 7

设置一个保存下标的数组qIndex

有如下规则
队尾放入规则：循环原数组 把小于的放入 qIndex队尾。如果大于等于那么弹出 qIndex队尾数据 直到某个值大于我们才放入队尾。【需要循环】
队头 弹出规则：过期的：【我猜想这就是为啥放入下标的原因】