题目描述：
1e5大小的nums[]数组中长度为k(1<=k<=1e5)的窗口的最大值
题解：
暴力求解O(n^2)会超时，需要O(nlogn)的解法
使用大根堆优先队列维护窗口元素，每次取最大值复杂度降为O(1)，堆结构维护复杂度O(logn)
问：如果维护窗口[l, r]前[0, l - 1]的元素不影响题目结果？
答：维护队头元素的下标在窗口[l, r]内即可。换句话说，在每次取队头元素之前，先判断队头元素是否在当前合法的窗口内，如果不合法就使其出队，如果合法那么队头元素就是当前窗口的最大值，因为窗口的移动间距为1，因此每次最多出队一个元素，因此查询最大值的复杂度最高为O(logn)
使用自定义内部类Pair维护(id, nums[id])
class Solution {
class Pair{
int id = 0;
int val = 0;
Pair(int id, int val) {
this.id = id;
this.val = val;
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
Queue<Pair> pq = new PriorityQueue<>((o1, o2) -> {
if(o1.val != o2.val) return o2.val - o1.val;
return o1.id - o2.id;
});
int len = nums.length;
int[] ans = new int[len - k + 1];
for(int i = 0; i < k; ++ i ){
pq.offer(new Pair(i, nums[i]));
}
ans[0] = pq.peek().val;
int st = 0;
for(int i = k; i < len; ++ i ) {
pq.offer(new Pair(i, nums[i]));
while(pq.peek().id < i - k + 1) pq.poll();
ans[++ st] = pq.peek().val;
}
return ans;
}
}
使用int[]维护(id, nums[id])
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
if(o1[1] != o2[1]) return o2[1] - o1[1];
return o1[0] - o2[0];
});
int len = nums.length;
int[] ans = new int[len - k + 1];
for(int i = 0; i < k; ++ i ) {
pq.offer(new int[]{i, nums[i]});
}
ans[0] = pq.peek()[1];
int st = 0;
for(int i = k; i < len; ++ i ) {
pq.offer(new int[]{i, nums[i]});
while(pq.peek()[0] < i - k + 1) pq.poll();
ans[++ st] = pq.peek()[1];
}
return ans;
}
}