239. Sliding Window Maximum

Priority Queue

class Solution {
    private static class Element {
        private final int value;
        private final int index;

        public Element(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }

        int[] res = new int[nums.length - k + 1];

        Queue<Element> maxHeap = new PriorityQueue<>((o1, o2) -> o2.value - o1.value);
        for (int i = 0; i < k - 1; i++) {
            maxHeap.offer(new Element(nums[i], i));
        }

        for (int j = k - 1; j < nums.length; j++) {
            maxHeap.offer(new Element(nums[j], j));
            int i = j - k + 1; // window: [i, j]
            int evictedIndex = i - 1;

            while (maxHeap.peek().index <= evictedIndex) {
                maxHeap.poll();
            }
            res[j - k + 1] = maxHeap.peek().value;
        }

        return res;
    }
}

Monotonic Queue

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];

        // 非严格单调递增队列，栈中存储的值，允许包含重复值，first -> ... -> last
        Deque<Integer> increaseDeque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            while (!increaseDeque.isEmpty() && num > increaseDeque.getFirst()) {
                // 当前 num 比队首元素大，则队首元素可以安全移除，因为更大的元素出现了
                increaseDeque.removeFirst();
            }
            increaseDeque.addFirst(num); // 将当前元素添加至队首

            int evictedIndex = i - k; // 注意此处是与队尾元素即最大元素比较，可以用 nums = [7, 2, 4], k = 2 验证。原因为只要窗口内出现了比窗外元素大的元素，则窗外元素会被从队列里移除，唯一可能使窗外元素留在队列里的原因只能为窗口内未出现比窗外元素大的元素，此时窗外元素位于队尾
            if (evictedIndex >= 0 && increaseDeque.getLast() == nums[evictedIndex]) {
                increaseDeque.removeLast();
            }

            if (i >= k - 1) {
                // 此时可以收集最大值
                res[i - k + 1] = increaseDeque.getLast();
            }
        }

        return res;
    }
}

注意存储值时需要包含重复值，否则 nums = [-7,-8,7,5,7,1,6,0], k = 4 会因为没有重复值导致出现最大元素与窗口外元素值相同而使最大值被移除的问题而无法 AC。

Monotonic Queue

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];

        Deque<Integer> increaseDeque = new LinkedList<>(); // 单调递增队列，栈中存储的为索引，first -> ... -> last

        for (int i = 0; i < nums.length; i++) {
            // 因为后续移除窗口外元素时采用的索引移除，所以队列中存储的值是否重复都没关系，此处的比较使用大于等于或仅大于都能 AC
            while (!increaseDeque.isEmpty() && nums[i] >= nums[increaseDeque.getFirst()]) {
                // 出现了大于等于之前队列左侧的元素，移除队列左侧之前的元素
                increaseDeque.removeFirst();
            }

            increaseDeque.addFirst(i); // 将当前元素索引添加至队列左侧

            int evictedIndex = i - k;
            if (increaseDeque.getLast() == evictedIndex) {
                increaseDeque.removeLast();
            }

            if (i >= k - 1) {
                ans[i - k + 1] = nums[increaseDeque.getLast()];
            }
        }

        return ans;
    }
}

References

239. Sliding Window Maximum
剑指 Offer 59 - I. 滑动窗口的最大值