239. Sliding Window Maximum

naive比较方法，O(kn)

public ArrayList<Integer> maxInWindows(int [] num, int size)
{
    if (size == 0) return new ArrayList<>();
    ArrayList<Integer> res = new ArrayList<>();
    int length = size - 1;
    for (int i = 0; i < num.length - length; i++) {
            res.add(findMax(num, i, i + length));
    }
    return res;
}

public int findMax(int[] num, int i, int j) {
    int max = num[i];
    for (int k = i; k <= j; k++) {
        if (num[k] > max) max = num[k];
    }
    return max;
}

双向队列

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length== 0 || k <= 0) return new int[0];
    int length = nums.length;
    int[] res = new int[length - k + 1];
    int resIndex = 0;
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < length; i++) {
        while (!q.isEmpty() && q.peek() < i - k + 1) q.poll(); // poll elements out of range(k - 1)
        while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) q.pollLast();
        q.offer(i);
        if (i >= k - 1) res[resIndex++] = nums[q.peek()]; // start filling result after k - 1
    }
    return res;
}