11.滑动窗口最大值

raylan.chen大约 2 分钟

一直想着使用双端队列来维持一个单调递增队列（队列的队尾是滑动窗口的最大值），

但是事实上对于本题来说，维持一个单调递减队列才是明智的选择。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // LinkedList 维持单调队列
        if (nums.length < k) return new int[0];
        // 返回值
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        // add(int index, E element)，List 接口声明的方法
        LinkedList<Integer> deque = new LinkedList<>();
        // 初始化单调队列
        deque.offerLast(nums[0]);
        for (int i = 1; i < k; i++) {
            // 单调递增队列
            if (deque.peekLast() < nums[i]) deque.offerLast(nums[i]);
            else {
                // 涉及到中间插入，较为复杂
                int j = deque.size();
                while (j > 0 && nums[i] < deque.get(j - 1)) j--;
                deque.add(j, nums[i]);
            }
        }
        res[index++] = deque.peekLast();
        // 遍历数组
        for (int i = 1, j = k; i < nums.length - k + 1 && j < nums.length; i++, j++) {
            // 涉及到中间删除，较为复杂
            deque.remove(Integer.valueOf(nums[i - 1]));
            if (deque.isEmpty() || deque.peekLast() < nums[j]) deque.offerLast(nums[j]);
            else {
                // 涉及到中间插入，较为复杂
                int x = deque.size();
                while (x > 0 && nums[j] < deque.get(x - 1)) x--;
                deque.add(x, nums[j]);
            }
            res[index++] = deque.peekLast();
        }
        return res;
    }
}

遇到 nums 长度较长、k 较大时，超出时间限制。

优秀题解

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.removeFirst();
            // 保持 deque 递减
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.removeLast();
            deque.addLast(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res[i] = deque.peekFirst();
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/sliding-window-maximum/solutions/2361228/239-hua-dong-chuang-kou-zui-da-zhi-dan-d-u6h0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

11.滑动窗口最大值

11.滑动窗口最大值

参考链接

个人尝试（❌错误）

优秀题解