My code:

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            int[] ret = new int[0];
            return ret;
        }
        int[] ret = new int[nums.length - k + 1];
        
        
        int pre = -1;
        
        for (int i = 0; i <= nums.length - k; i++) {
            if (pre < i) {
                if (pre >= 0 && nums[i + k - 1] >= nums[pre]) {
                    pre = i + k - 1;
                    ret[i] = nums[pre];
                }
                else {
                    int max = i;
                    for (int j = i + 1; j < i + k; j++) {
                        if (nums[j] >= nums[max]) {
                            max = j;
                        }
                    }
                    pre = max;
                    ret[i] = nums[pre];
                }
            }
            else {
                if (nums[i + k - 1] >= nums[pre]) {
                    pre = i + k - 1;
                }
                ret[i] = nums[pre];
            }
        }
        
        return ret;
    }
}

我自己的解法比較單純，沒用什么額外的數(shù)據(jù)結(jié)構(gòu)。
就是維持一個(gè)指針指向上一層的最大數(shù)的index。如果有多個(gè)數(shù)最大且相等，這個(gè)index選他們之中最大的index
然后邏輯比較簡(jiǎn)單。
如果這個(gè)指針在當(dāng)前范圍之外，那么這個(gè)數(shù)就不用在考慮了。
此時(shí)，如果新加進(jìn)來的數(shù)比他更大，那么直接更新指針。
如果小，那么就得遍歷當(dāng)前范圍，找出最大的那個(gè)值，更新指針。
如果在范圍之內(nèi)，那么就和新加進(jìn)來的數(shù)比較一下，更新指針。

然后看到了用 Deque 的解法。自己寫了下。

My code:

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            int[] ret = new int[0];
            return ret;
        }
        int[] ret = new int[nums.length - k + 1];
        
        Deque<Integer> q = new ArrayDeque<Integer>();
        int counter = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
                q.pollLast();
            }
            
            q.offerLast(i);
            if (i >= k - 1) {
                ret[counter] = nums[q.peek()];
                counter++;
            }
        }
        
        return ret;
    }
}

reference:
https://discuss.leetcode.com/topic/19055/java-o-n-solution-using-deque-with-explanation/2

對(duì)Deque的API不是很熟悉。
參考：
https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

他的思想就是類似于一種插入排序，從大到下。只不過把尾部（右側(cè)）比自己小的都刪除了。然后每次最大的值都在頭部（左側(cè)）。
同時(shí)每次都得把不在范圍內(nèi)的index都刪除掉。
差不多就這樣了。

q.pollFirst(), 對(duì)應(yīng)最左側(cè)
q.pollLast(), 對(duì)應(yīng)最右側(cè)

Anyway, Good luck, Richardo! -- 09/03/2016