写点什么

【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; }
复制代码

总结

  • 上述代码的时间复杂度是 O(n), 空间复杂度是 O(k)

  • 坚持每日一题,加油!我会继续更新算法题目,也欢迎算法爱好者一起交流学习。

发布于: 刚刚阅读数: 5
用户头像

Albert

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】滑动窗口的最大值Java题解_LeetCode_Albert_InfoQ写作社区