September 21, 2019

239. Sliding Window Maximum

Sol 1 暴力解

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }
        int maxVal = 0;
        int[] maxWindow = new int[nums.length - k + 1];
        int index = 0;
        for (int i = k; i <= nums.length; i++) {
            int curMaxVal = Integer.MIN_VALUE;
            for (int j = i - k; j < i; j++) {
                curMaxVal = Math.max(curMaxVal, nums[j]);
            }
            maxWindow[index] = curMaxVal;
            index ++;
        }
        return maxWindow;
    }
}

Sol 2 单调队列 Monotonic Queue

参考花花酱 LeetCode 239. Sliding Window Maximum。

用单调递减队列。每次新进队列一个元素，踢掉队列里存在的比这个元素小的所有元素。这样队列就是一个单调递减队列。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }
        Deque<Integer> queue = new LinkedList<>();
        int[] maxSlidingWindow = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && queue.peekFirst() < i - k + 1) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);

            if (i >= k - 1) {
                maxSlidingWindow[i - k + 1] = nums[queue.peekFirst()];
            }
        }
        return maxSlidingWindow;
    }
}