239. 滑动窗口最大值

239. 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] ans = new int[len + 1 - k];
        // 构造大顶堆，堆中元素对为<数组中的数， 索引>， 索引用于判断是否在窗口中
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((o1, o2)->(o2[0] != o1[0] ? o2[0] - o1[0] : o2[1] - o1[1]));
        for (int i = 0; i < k; i++) {
            maxHeap.add(new int[]{nums[i], i});
        }
        ans[0] = maxHeap.peek()[0];
        for (int i = k; i < len; i++) {
            maxHeap.add(new int[]{nums[i], i});
            // 当前的最大不在窗口中就删除
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            ans[i - k + 1] = maxHeap.peek()[0];
        }
        return ans;
    }
}