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

队列--滑动窗口最大值

作者: 暮想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;
        }
    

    相关文章

      网友评论

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

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