写点什么

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

用户头像
HQ数字卡
关注
发布于: 2 小时前

题目描述

给定一个数组 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著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 滑动窗口求最大值是经典问题,首先可以用朴素解法求解。也可以采用单调队列这种数据结构来解决,每次比较队尾元素,保持队首元素的最值。

代码

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)

  • 坚持每日一题,加油!

发布于: 2 小时前阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

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