江苏林润建设工程有限公司网站,开发一个非常简单的聊天软件,wordpress 免费 主题 下载,微信官网电脑版下载给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 输入#xff1a;nums [1,3,-1,-3,5,3,6,7], k 3
输出#xff1a;[3,3,5,… 给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7 如果你刚看见这道题你会怎么想三秒告诉我3...2...1...时间到 首先是滑动窗口一听到这个名字我们就应该立刻的想到双指针双指针这个大方向是错不了我们再看要每次取到范围内的最大值除了最大堆就是优先队列可以做到这件事接下来我们先用最大堆进行解题 最大堆就是其实就是一棵树通过上浮和下浮使得堆顶是最大值或者最小值Java中默认是最小堆所以我们如果是想每次取到范围内的最大值 PriorityQueueInteger queuenew PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;//最大值 默认是o1-o2}}); 需要对堆的比较器进行重写,构造一个最大堆 维护一个一个列表进行最大值的维护 ListInteger listnew ArrayList(); for(int right0;right nums.length;right){if(rightk-1){queue.offer(nums[right]);}else{queue.offer(nums[right]);list.add(queue.peek());queue.remove(nums[left]);}}
结果不出意外 怎么办时间超时了怎么办堆的上浮和下沉确实浪费了大量的时间所以我们使用另外一种数据结构解决本题优先队列 //维护一个单调队列class MaxQueue{private LinkedListInteger queuenew LinkedList();//添加public void push(int x){ //队列不为空队尾元素如果小于当家加入元素直接扔出去while(!queue.isEmpty()queue.getLast()x){queue.pollLast();}queue.addLast(x);}//删除public void pop(int x){if(xqueue.getFirst()){queue.pollFirst();}}//得到最大值public Integer getMax(){return queue.getFirst();}} 核心代码 int left0;for(int right0;right nums.length;right){if(rightk-1){window.push(nums[right]);}else{window.push(nums[right]);list.add(window.getMax());window.pop(nums[left]);}}
结果不出意外 上源代码 public int[] maxSlidingWindow(int[] nums, int k) {if(numsnull){return null;}MaxQueue windownew MaxQueue();ListInteger listnew ArrayList();int left0;for(int right0;right nums.length;right){if(rightk-1){window.push(nums[right]);}else{window.push(nums[right]);list.add(window.getMax());window.pop(nums[left]);}}return list.stream().mapToInt(Integer::valueOf).toArray();}//维护一个单调队列class MaxQueue{private LinkedListInteger queuenew LinkedList();//添加public void push(int x){while(!queue.isEmpty()queue.getLast()x){queue.pollLast();}queue.addLast(x);}//删除public void pop(int x){if(xqueue.getFirst()){queue.pollFirst();}}//得到最大值public Integer getMax(){return queue.getFirst();}}
