239. 滑动窗口最大值（优先队列）

痛定思痛。 2022-09-11 13:14 168阅读 0赞

## 题目重述 ##

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

### 示例 1： ###

输入：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       3
     1 [3  -1  -3] 5  3  6  7       3
     1  3 [-1  -3  5] 3  6  7       5
     1  3  -1 [-3  5  3] 6  7       5
     1  3  -1  -3 [5  3  6] 7       6
     1  3  -1  -3  5 [3  6  7]      7

### 示例 2： ###

输入：nums = \[1\], k = 1  
输出：\[1\]

### 示例 3： ###

输入：nums = [1,-1], k = 1
    输出：[1,-1]

### 示例 4： ###

输入：nums = [9,11], k = 2
    输出：[11]

### 示例 5： ###

输入：nums = [4,-2], k = 2
    输出：[4]

### 提示： ###

1 <= nums.length <= 105
    -104 <= nums[i] <= 104
    1 <= k <= nums.length

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/sliding-window-maximum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

*  优先队列实现，使用大顶堆
 *  需要注意的是 不断add到队列的时候，有可能最大值即堆顶不一定是该滑动窗口的值，那怎么保证呢？答案是存储值的时候顺便存储下标即可，即判断下标是不是小于等于`i-k`的，如果是，说明不是该滑动窗口的，poll即可，否则就是该滑动窗口的最大值

## Java实现 ##

class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
           PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
        
               public int compare(int[] pair1,int[] pair2){
        
                   // 大顶堆，且角标往后稍稍
                   return pair1[0]!=pair2[0]? pair2[0]-pair1[0]:pair2[1]-pair1[1];
               }
           });
           for(int i=0;i<k;i++){
        
               pq.offer(new int[]{
        nums[i],i});
           }
           int[] ans = new int[nums.length-k+1];
           ans[0] = pq.peek()[0];
           for(int i=k;i<nums.length;i++){
        
               pq.offer(new int[]{
        nums[i],i});
               while(pq.peek()[1]<= (i-k)){
        
                   pq.poll();
               }
               ans[i-k+1] = pq.peek()[0];
           }
           return ans;
        }
    }