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

生成窗口的最大值数组　

　　

　　给定一个n个元素的整型数组arr，和一个大小为w的窗口，从数组的最左边移动到最右边，每次移动一个单位，一共产生n-w+1个窗口的最大值数组。

　　例如数组为[4,3,5,4,3,3,6,7]，窗口大小为3时，

　　[4  3  5]  4  3  3  6  7   窗口中最大值为5

　　4  [3  5  4]  3  3  6  7   窗口中最大值为5

　　4  3  [5  4  3]  3  6  7   窗口中最大值为5

　　4  3  5  [4  3  3]  6  7   窗口中最大值为4

　　4  3  5  4  [3  3  6]  7   窗口中最大值为6

　　4  3  5  4  3  [3  6  7 ]  窗口中最大值为7

　　要求实现一个函数，输入为整型数组arr，窗口大小为w，输出为一个长度为 n-w+1 的数组res，res[i]表示每一种窗口状态下的最大值。以本题为例，结果应该返回[5,5,5,4,6,7]

　

package com.test;

import java.util.LinkedList;

/**
 * Created by Demrystv.
 */
public class GetMaxWindow {
    public int[] getMaxWindow(int[] arr,int w){
        if (arr.length<w || w<1 || arr==null){
            return null;
        }

        //双端队列qmax存放的是数组arr中的下标
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;

        //qmax的放入规则是：
        // 如果qmax为空，则直接将下标i 放入，该过程结束
        // 如果qmax不为空，则取出当前qmax队尾元素的下标，记为j
        //     如果arr[j]>arr[i]，则将i放入qmax的队尾
        //     如果arr[j]<=arr[i]，则将j从qmax中弹出
        //qmax的弹出规则是：
        // qmax的队头下标等于i-w，说明已经过期，将其弹出
        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;
    }
}