剑指Offer59-Ⅰ—滑动窗口的最大值（java版）

本文主要是介绍剑指Offer59-Ⅰ—滑动窗口的最大值（java版），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述：

标签：队列  滑动窗口  单调队列  堆（优先队列）

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

代码：

 思路分析：

维护一个大小为k的大顶堆，每次将大顶堆的堆顶加入到list中，这里要注意的是想要移除队列中的某个元素只要使用queue.remove(该元素的值)即可。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k == 0 || nums.length == 0){
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for(int i = 0;i < k;i++){
            queue.add(nums[i]);
        }
        list.add(queue.peek());
        for(int i = 0, j = i + k;j < nums.length;i++, j++){
            queue.remove(nums[i]);
            queue.add(nums[j]);
            list.add(queue.peek());
        }

        int[] ans = new int[list.size()];
        int cnt = 0;
        for(int num : list){
            ans[cnt++] = num;
        }
        return ans;
    }
}

这篇关于剑指Offer59-Ⅰ—滑动窗口的最大值（java版）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！