滑动窗口的最大值

1. 暴力解法：

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] a, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (a == null || size > a.length || size == 0) {
            return ret;
        }
        for (int i = 0, j = size - 1; j < a.length; ++i, ++j) {
            int max = max(a, i, j);
            ret.add(max);
        }
        return ret;
    }

    private int max(int[] a, int l, int r) {
        int max = Integer.MIN_VALUE;
        for (int i = l; i <= r; ++i) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }
}

2. 大顶堆解法

import java.util.*;
public class Solution {
    private PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b.compareTo(a)); // 大顶堆

    public ArrayList<Integer> maxInWindows(int [] a, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (a == null || size > a.length || size == 0) {
            return ret;
        }
        for (int i = 0, j = size - 1; j < a.length; ++i, ++j) {
            if (i == 0) {
                for (int k = i; k <=j; ++k) {
                    heap.offer(a[k]);
                }
            } else {
                heap.remove(a[i - 1]);
                heap.offer(a[j]);
            }
            int max = heap.peek();
            ret.add(max);
        }
        return ret;
    }
}

3. 单调队列解法

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] a, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (a == null || size > a.length || size == 0) {
            return ret;
        }

        Deque<Integer> dq = new LinkedList<>(); // dq里面存的是下标
        for (int i = 0; i < a.length; ++i) {
            while (!dq.isEmpty() && a[dq.peekLast()] < a[i]) {
                // 单调递减队列
                dq.pollLast();
            }
            dq.offerLast(i);
            if (dq.peekFirst() + size <= i) {
                // i代表了窗口的右端，此时已经越过了队列头的值
                dq.pollFirst();
            }
            if (i + 1 >= size) {
                // 说明已经可以形成窗口
                ret.add(a[dq.peekFirst()]);
            }
        }
        return ret;
    }
}