劍指offer 滑動視窗問題

給定一個數組和滑動視窗的大小，找出所有滑動視窗裡數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動視窗的大小3，那麼一共存在6個滑動視窗，他們的最大值分别為{4,4,6,6,6,5}；針對數組{2,3,4,2,6,2,5,1}的滑動視窗有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

本人思路：

每次滑動，總是減去一個值，新增一個值；如果新增值大于上一個視窗的最大值，那麼新增值為本視窗的最大值；否則，如果上一個視窗最大值大于移除的那個元素，則上一個視窗的最大值為本視窗最大值；如果移除元素為上一個視窗最大值，則将本視窗所有元素統計最大值。

public class Window  {
    public static void main(String args[]){
        int A[] = new int[]{10,9,8,7,6,5,4,3,2,1};
        int size = 3;
//        int result[] = getMaxinWindow(A, size);
//        Print.printArray(result);

        Window win = new Window() ;
        ArrayList<Integer> ers = win.maxInWindows(A,size);
        Print.printArray(ers);
    }

    /**
     * 獲得每個滑動視窗最大值
     * @param params ： 已知數組
     * @param size ： 滑動視窗大小
     * @return
     */
    public static int[] getMaxinWindow(int[] params, int size){
        // 參數檢查
        if(params == null|| params.length < 1 || size < 1 || size > params.length){
            return null ;
        }
        // 最大值個數為 params.length + 1- size
        int[] result = new int[params.length - size + 1] ;
        // 第一個滑動視窗最大值
        for(int i= 0 ; i< size ; i ++){
            if(result[0] < params[i]){
                result[0] = params[i];

            }
        }
        for (int i = size; i < params.length; i++) {
            if (params[i] >= result[i - size]) { /// 目前值大于等于前面視窗所有值則目前值為新視窗最大值
                result[i - size + 1] = params[i];
            } else if (result[i - size] > params[i - size]) { // 目前值小于最大值，且最大值沒有被移除，新視窗最大值為上一個視窗最大值
                result[i - size + 1] = result[i - size];
            } else{ // 重新計算目前視窗最大值
                int temp  = getMax(params, i -size + 1, i) ;
                if(temp == Integer.MIN_VALUE){
                   return null ;
               }
                result[i - size + 1] = temp;
            }
        }
        return result ;
    }

    private static int getMax(int[] params, int i, int i1) {
        if(params == null || i < 0 || i1 < i || i1 > params.length){
            return Integer.MIN_VALUE ;
        }
        int max = params[i] ;
        for(int temp = i ; temp <= i1 ; temp ++){
            if(max < params[temp]){
                max = params[temp];
            }
        }
        return  max ;
    }
}

經過運作，本算法可以正常得出結果。算法的時間複雜度為介于O（n）和O(n*k)之間, n為數組中元素個數，k為視窗大小。

如果數組為降序排列，時間複雜度為O(n * k) 。

在網上搜尋，發現了另外一種解法見連結 http://blog.csdn.net/sbq63683210/article/details/51707589

這種解法采用了雙端隊列的資料結構，每次得到的視窗最大值的索引都放在隊列的頭部；并且隊列保持的索引，在數組中為非降序排列。每次隊列頭部儲存的索引要麼移除，要麼保留。然後根據非降序規則添加新的索引進來。這樣有效排除了，視窗中小于目前值的元素。這種算法的時間複雜度為O（n）。