【LeetCode】滑动窗口的最大值 Java 题解

作者：Albert

2022 年 10 月 10 日
北京
本文字数：1238 字
阅读完需：约 4 分钟

题目描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7] 解释: 
  滑动窗口的位置                最大值---------------               -----[1  3  -1] -3  5  3  6  7       3 1 [3  -1  -3] 5  3  6  7       3 1  3 [-1  -3  5] 3  6  7       5 1  3  -1 [-3  5  3] 6  7       5 1  3  -1  -3 [5  3  6] 7       6 1  3  -1  -3  5 [3  6  7]      7
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组题目，题目求的是滑动窗口的最大值。这个题目的题意容易理解，我们可以每次划分一个长度为 k 的区间，然后取出区间内的最大值。数组的长度是 n, 单个区间的长度是 k, 滑动窗口的区间个数是 n - k + 1。使用朴素算法，取出每个区间的最大值的时间复杂度是 O(k), 总的时间复杂度是是 O(k * (n - k + 1))。
在使用朴素算法的时候，时间复杂度较高，不能通过全部测试用例。我们需要优化朴素算法的重复计算。可以维护一个单调队列来解决。在单调队列算法中，我们逐个比较队尾元素和当前元素 nums[i]的大小，如果对尾元素比 nums[i]小，则出队列。在队列中只保留较大的元素。同时，为了避免较大的窗口在滑动过程中，漏掉较大元素的出队。在 i >= k 的时候，优先判断队首元素是否应该出队，保证队列的正确性。
在 Java 中，双端队列我们一般使用 Deque 数据结构。Deque 是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行，使用起来比较方便。
具体实现代码如下，供参考。

通过代码

public int[] maxSlidingWindow(int[] nums, int k) {        int n = nums.length;        if (n == 0 || k == 0) {            return new int[0];        }
        Deque<Integer> deque = new LinkedList<>();        int[] ans = new int[n - k + 1];        for (int i = 0; i < k; i++) {            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {                deque.removeLast();            }            deque.addLast(nums[i]);        }        ans[0] = deque.peekFirst();        for (int i = k; i < n; i++) {            if (deque.peekFirst() == nums[i - k]) {                deque.removeFirst();            }            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {                deque.removeLast();            }            deque.addLast(nums[i]);            ans[i - k + 1] = deque.peekFirst();        }        return ans;    }