题目概述:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回每个滑动窗口中的最大值
解题思路:这道题的难点在于需要在维护一个滑动窗口的同时,维护这个窗口中的最大值。通过滑动窗口那一节的练习,我们已经可以很轻松的去维护一个滑动窗口了,通常我们使用set或map数据结构。但在这道题中这两个数据结构都不适用,set它不能存储重复数字,而map又难以维护最大值。那么有没有同时可以维护这两个操作的数据结构呢?当然有,那就是优先队列(堆)——PriorityQueue。我们可以创建一个大根堆,堆中存储一个Pair值,每个Pair代表某个元素的索引值和数值,按照数值从大到小排序,如果数值一致,索引小的在前。每次从堆中取出数,判断这个数是否在滑动窗口中,如果在,那么这个数就是该滑动窗口的最大值,否则从堆中移除该元素。
时间复杂度:\(O(n)\)
代码:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int res[] = new int[n - k + 1];
//创建大根堆
PriorityQueue<Pair<Integer,Integer>>heap = new PriorityQueue<>(new Comparator<Pair<Integer,Integer>>(){
public int compare(Pair<Integer,Integer> a,Pair<Integer,Integer> b){
if(a.getKey() != b.getKey())return b.getKey() - a.getKey();
return a.getValue() - b.getValue();
}
});
for(int i = 0; i < k; i ++)heap.offer(new Pair<Integer,Integer>(nums[i],i));
int t = 0;
res[t++] = heap.peek().getKey();
for(int i = k; i < n; i ++){
heap.offer(new Pair<Integer,Integer>(nums[i],i));
// 判断是否在当前滑动窗口中
while(i - k >= heap.peek().getValue()){
heap.poll();;
}
res[t++] = heap.peek().getKey();
}
return res;
}
}