第八章（三）滑动窗口

其实滑动窗口类似队列一样，对一些数组区间挺好用的

滑动窗口

输入一个长度为n的序列，寻找尽量长的子序列，使得该子序列中没有相同的元素

思路：每次进来一个a[R]，窗口拉伸用map记录出现的元素的下标，如果a[R]的已经出现过并且上次出现的下标值位于[L,R]区间，判断当前子序列[L,R-1]的长度是否更新，再更新L为a[R]上次出现过的下标值+1，这时子序列的区间为[L,R]。如果a[R]并没有出现过，将a[R]放入map中，并更新[L,R]这一段为新的子序列。

/**
     * 输入一个长度为n的序列，寻找尽量长的子序列，使得该子序列中没有相同的元素
     */
    public static void getMin(int[] a) {
        int L=0,maxL=0,maxR=0;
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int R=0;R<a.length;R++) {
            if(map.get(a[R])==null||map.get(a[R])<L) {
                map.put(a[R], R);
                if(R-L>maxR-maxL) {//[L,R]
                    maxR=R;maxL=L;
                }
            }else {//碰到相同的了[L,R-1]->[上次出现的位置+1,R]
                if(R-L-1>maxR-maxL) {
                    maxR=R-1;maxL=L;
                }
                L=map.get(a[R])+1;
            }
        }
        System.out.println("L:"+maxL+" R:"+maxR+" length:"+(maxR-maxL+1));
    }
    public static void main(String[] args) {
        int[]a= {3,4,5,1,2,4,5,3,6};
        getMin(a);
    }

滑动窗口+数据结构

滑动窗口的最小值问题：输入正整数k和一个长度为n的整数序列，f(i)表示从元素i开始连续k个元素的最小值，计算出0-(n-k)的最小值

思路：数据结构+滑动窗口，每一个新的元素进来如果他比之前的某些元素小，那么这些元素就不可能再成为最小值。如果他是最大的那么也要插入，因为随着区间的缩短，最小的被输出了那么很有可能会成为最小的。单调队列的话，最小值永远是队头，关键问题是如何知道这个最小值是在这个区间的那个位置，即什么时候更新队头，试想一下，这个最小值如果已经达到区间的边缘那么他们两个应该相等，这个时候应该移动队头，因为如果一个区间内的最小值重复出现，那么在插入的时候就要注意插入多次即可。

/**
     * 滑动窗口的最小值问题：输入正整数k和一个长度为n的整数序列
     * f(i)表示从元素i开始连续k个元素的最小值，计算出0-(n-k)
     * 单调队列来实现
     */
    public static void getMin(int[] a,int k) {
        int[]s=new int[10];
        int rear=0;
        for(int i=0;i<k;i++) {
            while(rear>0&&a[i]<s[rear-1]) {
                rear--;
            }
            s[rear++]=a[i];
        }
        int front=0;
        for(int i=0;i<a.length-k;i++) {
            System.out.println("f("+i+")="+s[front]);
            if(s[front]==a[i]) {
                front++;
            }
            while(rear>front&&a[k+i]<s[rear-1]) {
                rear--;
            }
            s[rear++]=a[k+i];
        }
        System.out.println("f("+(a.length-k)+")="+s[front++]);
    }
    public static void main(String[] args) {
        int[]a= {6,7,8,9,1,2,3};
        getMin(a,3);
    }