美文网首页数据结构与算法
队列--滑动窗口最大值

队列--滑动窗口最大值

作者: 暮想sun | 来源:发表于2020-01-08 15:19 被阅读0次

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
思路:每K个数据,使用优先级队列。数据大的优先级高。

 public static int[] maxSlidingWindow(int[] nums, int k) {

        if (nums.length == 0) {
            return new int[k];
        }
        int[] maxNums = new int[nums.length - k + 1];

        int i = 0;
        while (i <= nums.length - k) {
            PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
            int target = i + k - 1;
            int j = i;
            while (j <= target) {
                queue.add(nums[j]);
                j++;
            }
            maxNums[i] = queue.peek();
            i++;
        }

        return maxNums;
    }

相关文章

  • 剑指offer 59-1 滑动窗口内的最大值

    给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。 使用一个队列记录滑动窗口内的最大值....

  • 59.队列的最大值(中等)

    考点:本题考查队列和知识迁移能力 题目一描述:滑动窗口的最大值 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数...

  • 2020-04-06 刷题1(队列)

    滑动窗口的最大值 用一个双向队列(两边都开口)deque来存放滑动窗口中可能成为最大值的下标,每读到一个新的数时,...

  • 0239-滑动窗口最大值

    滑动窗口最大值 方案一 用双向队列保存数字的下标,遍历整个数组,如果此时队列的首元素是i - k的话,表示此时窗口...

  • LeetCode 239 滑动窗口最大值 Sliding Win

    有关栈、堆、队列的LeetCode做题笔记,Python实现 239. 滑动窗口最大值 Sliding Windo...

  • 队列--滑动窗口最大值

    给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 ...

  • 2020-03-30

    针对滑动窗口最大值的思考与代码优化239解题思路,单调队列。进出队列,就是下标。 当时,想建立队列,单独提出来,以...

  • 队列的最大值

    滑动窗口的最大值给定一个数组和滑动窗口的最大值,找出所有滑动窗口里的最大值。例如输入[2, 3, 4, 2, 6,...

  • 常见队列问题

    滑动窗口的最大值给定一个数组和窗口长度k,求每个窗口内的最大值 解题思路使用双端队列 从队尾加入新元素,从对头取出...

  • 每日一题之《剑指offer》64,65,66,67题

    第64题:滑动窗口的最大值 难易度:⭐⭐⭐ 解析:本题的思路是使用双端队列双端队列用来保存窗口最大数值的index...

网友评论

    本文标题:队列--滑动窗口最大值

    本文链接:https://www.haomeiwen.com/subject/gprsactx.html