class Solution {
    //优先队列存储当前元素值和索引，用大顶堆进行排序
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 1) {
            return nums;
        }
        int[] res = new int[n - k + 1];
        //初始化大顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[0] - a[0]);
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i],i});
        }
        res[0] = pq.peek()[0];
        int j = 1;
        for (int i = k ; i < n; i++) {
            pq.offer(new int[]{nums[i],i});
            while (pq.peek()[1] < i - k + 1) { //滑动窗口的右边界k，左边界i-k+1
                pq.poll();
            }
            res[j++] = pq.peek()[0];
        }
        return res;
    }
}