239.滑动窗口最大值

1.一刷

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

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

1. Deque是LinkedList类实现的一个双端队列的接口，Deque<Integer> deque=new LinkedList<>()。

• 	首元素	首元素	尾元素	尾元素
  	抛出异常	特殊值	抛出异常	特殊值
  插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
  删除	removeFirst()	pollFirst()	removeLast()	pollLast()
  检查	getFirst()	peekFirst()	getLast()	peekLast()

2. 一开始看到滑动窗口先想到动规，但是这题动规的开销比较大。开辟O($n^2$)空间数组来保存状态。dp[i][j]表示下标从i到j的最大值。则dp[i][j]=Math.max(dp[i][j-1]，dp[i+1][j])，可以初始化第0行和第n列以及dp[i][i],然后需要从下往上，从左往右遍历来维护dp。
3. 固定窗口+最大值自然要能想到大根堆。其实就是一个有序的双端队列，这里队列存放的是数组的索引下标，每次窗口滑动进来一个元素出去一个元素。有两个问题需要考虑：

• 每次窗口移动时，堆顶元素最大值要考虑在不在当前窗口内，因此每次窗口滑动若当前队列的最大值的索引下标小于当前窗口的左边界则移出。

• 插入新元素时，要保证插入后队列保持有序。如果每次插入都是从小(队尾)到大(头)找到相应的位置插入，那么排序时间O(logn)(PriorityQueue底层基于堆实现)，总的时间复杂度O(nlogn)。

  实际上每次插入时，队列中比待插入元素小的都可以直接出队，因为插入元素肯定是在当前窗口的右边界，索引下标在比它小的元素的右边，所以该元素进队后肯定是轮不到比它小的元素作为最大元素出队的。因此可以直接出队，每个元素只进入一次队列出一次队列(被访问就要出)，因此排序时间O(1)，总时间O(n)。

 public int[] maxSlidingWindow(int[] nums, int k) {
 Deque<Integer> queue=new LinkedList<>();
     int[] res=new int[nums.length-k+1];
     for(int i=0;i<nums.length;i++)
     {
     while(!queue.isEmpty()&&queue.peek()<i-k+1) queue.poll();
     while(!queue.isEmpty()&&nums[queue.peekLast()]<nums[i]) queue.pollLast();
     queue.offer(i);
     if(i>=k-1)
     res[i-k+1]=nums[queue.peek()];
     }
 	return res;
   }

2.二刷+单调队列

• 获取最大值

维护一个递减的双端队列，队列的头节点就是最大值。

“当前元素”从队尾插入时，如果队尾元素小于“当前元素”，那么移除该元素，直到队尾元素大于等于“当前元素”时，插入“当前元素”。

• 窗口元素移除

根据以上元素插入的方法，显然队列的长度不能表征窗口大小。那么如何移除窗口之外的最大值？

遍历元素的过程中，可以直接通过下标 i-k 访问到当前窗口需要移除的元素，如果当前队首元素等于要移除的元素，直接将队首元素移除队列。从而保证每次取出队首元素作为的最大值一定是在当前窗口。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k==1) return nums;
        Deque<Integer> queue=new LinkedList<>();
        int[] res=new int[nums.length-k+1];
        int index=0;
        queue.offerLast(nums[0]);
        for(int i=1;i<nums.length;i++){
            while(queue.size()>0&&queue.peekLast()<nums[i]){
                queue.pollLast();
            }  
            queue.offerLast(nums[i]);
            //形成窗口
            if(i==k-1) res[index++]=queue.peekFirst();
            if(i>k-1){
                int del=nums[i-k];
                if(queue.peekFirst()==del) queue.pollFirst();
                res[index++]=queue.peekFirst();
            }
        }
        return res;
    }
}

3.三刷+TreeMap

使用TreeMap维护滑动窗口。其中key为滑动窗口里面的值，value为出现的次数：

• 最大值直接通过lastKey()拿到
• 移动过程中窗口元素删除，通过减少元素出现频次value实现

不同于单调队列，TreeMap可以保存维护滑动窗口内所有元素。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res=new int[nums.length-k+1];
        TreeMap<Integer,Integer> treemap=new TreeMap<>();
        for(int i=0;i<k;i++){
            treemap.put(nums[i],treemap.getOrDefault(nums[i],0)+1);
        }
        res[0]=treemap.lastKey();
        for(int i=k;i<nums.length;i++){
            if(treemap.get(nums[i-k])==1) treemap.remove(nums[i-k]);
            else treemap.put(nums[i-k],treemap.get(nums[i-k])-1);
            treemap.put(nums[i],treemap.getOrDefault(nums[i],0)+1);
            res[i-k+1]=treemap.lastKey();
        }
        return res;
    }
}