滑动窗口最大值

描述

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

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

示例

输入: 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum

题解

暴力破解

思路
遍历每个滑动窗口，在每个滑动窗口中获取最大值；
代码

  public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];

        int [] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++)
                max = Math.max(max, nums[j]);
            output[i] = max;
        }
        return output;
    }

复杂度分析
时间复杂度： 在nums数组中遍历获得滑动窗口O(N)，在滑动窗口中获取最大值的时间复杂度为O(k),
因为每一次遍历数组获取滑动窗口都需获取滑动窗口的最大值，
因此最终的时间复杂度为O(N*k);
空间复杂度：返回值所需O(N-l+1);

优先队列

思路
使用大顶堆来维护滑动窗口中的的数据，大顶堆的堆顶元素即为滑动窗口中最大值。
算法步骤：

1. 准备：

• 源数据nums数组，长度为N
• 滑动窗口大小k
• 优先队列（大顶堆）priorityQueue，大小需为k
• 结果数组results，长度为N-k+1

2. 初始化priorityQueue：由于滑动窗口是从nums的下标k-1开始遍历的,因此先
   使用nums中[0,k-1]上的值来初始化priorityQueue;
   nums[0,k-1]为第一个滑动窗口，因此results[0]为此时priorityQueue的最优先元素；
3. 遍历nums：从k到N遍历nums，下标为i,此时滑动窗口范围为nums[i-k+1,i],priorityQueue
   的值为nums[i-k,i-1]；
4. 调整优先队列：将nums[i]添加到priorityQueue，nums[i-k],从priorityQueue移除，
   保持priorityQueue的值与滑动窗口的值一致；
5. 添加滑动窗口最大值：优先队列的队首元素为滑动窗口此时的最大值，
   results[i-k+1]=priorityQueue的队首元素；
   代码

public class PriorityQueueSolution {
    Comparator<Integer> comparator = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
           return o2-o1;
        }
    };

    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (k > len || k < 1) {
            return new int[0];
        }
        int[] result = new int[len - k + 1];
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, comparator);
        //初始化优先队列
        int i = 0;
        while (i < k - 1) {
            queue.add(nums[i]);
            i++;
        }
        //从滑动窗口中获取最大值
        for (int right = k - 1; right < len; right++) {
            queue.add(nums[right]);
            if (queue.size() > k) {
                queue.remove(nums[right-k]);
            }
            result[right - k + 1] = queue.element();
        }
        return result;
    }
}

复杂度分析
时间复杂度： 在nums数组中遍历获得滑动窗口O(N)，优先队列删除、添加元素的复杂度为O(logk),
获取优先队列的队首元素的时间复杂度为O(1),
因此最终的时间复杂度为O(N*logk);
空间复杂度：返回值所需O(N-l+1),优先队列为O(k),最终为O(N);

双端队列

思路
使用双端队列来存储滑动窗口在nums中对应的下标；
双端队列限制：

• 靠近尾部的队列元素的值需要比靠近队首的元素的值要大，
  即当窗口滑动时，滑动窗口中增加的元素在nums的下标是从队尾添加的，
  滑动窗口移除的元素在nums中的下标是从队首移除的；
• 靠近尾部的队列元素的值作为下标在nums值需要比靠近队首的要小，
  即当队列添加下标之前要从队列队尾去除这些下标（它们在nums中对应的值要比要添加
  下标在nums中的要小）；
  经过上述限制，队列的队首下标在nums中对应的值始终是队列的最大值，即为滑动窗口中的最大值；
  代码

public class DequeSolution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (k > len || k < 1) {
            return new int[0];
        }
        int[] result = new int[len - k + 1];
        //用于存储在滑动窗口中有效的索引，且双端队列会从前向后维护一个降序的排列，
        // 获取滑动窗口中的最大值，只需要获取双端队列的首值即可
        Deque<Integer> indexDeque = new ArrayDeque<>(k);
        for (int i = 0; i < len; i++) {
            addAndRemove(nums, indexDeque, i, k);
            if (i >= k - 1) {
                result[i - k + 1] = nums[indexDeque.getFirst()];
            }
        }
        return result;
    }

    private void addAndRemove(int[] nums, Deque<Integer> indexDeque, int index, int k) {
        //如果indexDeque中的开始元素的索引在当前滑动窗口的范围之外删除
        if (indexDeque != null && indexDeque.size() > 0 && (index - indexDeque.getFirst()) > k - 1) {
            indexDeque.removeFirst();
        }
        //循环从indexDeque后部取出索引indexLast，与要添加的索引index，将它们在nums中的值比较，若值indexLast的值比较小，
        // 则将indexLast从indexDeque删除，这样可以保证indexDeque中的索引在nums中的取值是降序排列，也能保证indexDeque中的
        // 首个值是滑动窗口的最大值的索引
        while (indexDeque != null && indexDeque.size() > 0 && nums[index] > nums[indexDeque.getLast()]) {
            indexDeque.removeLast();
        }
        indexDeque.addLast(index);
    }
}

复杂度分析
时间复杂度： 在nums数组中遍历获得滑动窗口O(N)，双端队列删除、获取队首元素的复杂度为O(1);添加元素的复杂度为O(1)~O(logk),
因此最终的时间复杂度为O(N)~O(log(k));
空间复杂度：返回值所需O(N-l+1),双端队列为O(k),最终为O(N);

动态规划

思路
构造left,right数组；

• 将nums按k的大小分成多段，最后一段可能不到k个元素；
• left数组中，left中按分段与nums对应，left分段中从左到右对应索引的值，是nums对应分段中对应索引及之前的索引的之中最大的一个值
• right数组中，right中按分段与nums对应，right分段中从右到左对应索引的值，是nums对应分段中对应索引及之前的索引的之中最大的一个值
• 因此获取一个滑动窗口的最大值，是max(滑动窗口最左边位置的索引在right数组中的值,滑动窗口最右边位置的索引在left数组中的值

代码

public class DynamicProgrammingSolution implements ISolution {
    @Override
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (k > len || k < 1) {
            return new int[0];
        }
        int[] left=new int[len];
        int[] right=new int[len];
        //构造left、right数组
       for(int i=0;i<len;i++){
            //left构造
            if(i%k==0){
                left[i]=nums[i];
            }else{
                left[i]=Math.max(left[i-1],nums[i]);
            }

            //right构造,从nums数组右边开始遍历
            int index=len-i-1;
            if(index==len-1||(index+1)%k==0){
                right[index]=nums[index];
            }else{
                right[index]=Math.max(right[index+1],nums[index]);
            }
        }

        //获取滑动窗口最大值数组
        int[] result=new int[len-k+1];
        for(int i=0;i<len-k+1;i++){
            result[i]=Math.max(right[i],left[i+k-1]);
        }
        return result;
    }
}

复杂度分析
时间复杂度： 构造left，rigt数组O(N),在nums数组中遍历获得滑动窗口O(N).
因此最终的时间复杂度为O(2N);
空间复杂度：返回值所需O(N-l+1),left,right数组分别为O(N),最终为O(3N);