LeetCode239滑动窗口最大值

滑动窗口：这个概念应该是起源于计算网路的滑动窗口协议，是用来控制流量的。而在算法题中，滑动窗口的技巧常用在字符串和数组中得出子串或者子数组的一些极值的操作，关于滑动窗口更加形象的题目可以看leetCode上《和为s的连续正数序列》。

题目描述

定一个数组 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

题目解析

刚开始的时候看题目中说返回的是滑动窗口的最大值，但是示例中给出的输出又是一个数组，因此这里返回的其实由每个滑动窗口中最大值构成的一个数组。即我们需要在窗口每次滑动的时候取出该窗口元素内的最大值，直到最后一个元素。

解法1：

其实使用暴力的算法进行题解是很容易的，最外层循环从0遍历到nums.length - k + 1(最后一个窗口的右边界到达最后一个元素即可)。里面那层循环每次都重新计算滑动窗口内的最大值，即计算k个元素的最大值。代码如下：

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        if (nums.length * k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];    //最后返回数组的长度可以提前计算出来
        for (int i = 0; i < nums.length - k + 1; i++) {
    
            int max = Integer.MIN_VALUE;
            for (int j = i; j < k + i; j++) {
    
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        return result;
    }
}

leetCode中提交的时候超出时间限制了，很明显的其时间复杂度为O(len*k);

解法2

既然题目提示我们要用一个线性时间的问题求解，那么只能想一种方法进行一次遍历的时候就能够得到想要的答案了。看大佬讲到一种使用双端队列（进出在首尾都行）的方式来进行求解，大致思路如下：

1、 使用一个队列，每次将元素入队，如果当前元素进入队列中，要比队列中的某个元素要大，则将这些比之小的元素出队，之后再将该元素入队。这样每次判断的操作能够保证队列中的元素是按照递减的顺序排列的。（注意在这个操作过程也有可能将队列中的元素全部删除）

2、从i = k - 1开始，i为遍历的数组下标索引，每次取得队头元素（因为队头元素是最大的），加入到要返回的结果数组中。

下面看一张图（大佬画的，真是清晰明了，原文链接《滑动窗口最大值》）

 
程序实现代码如下，java语言实现的，使用的了其内置的集合框架：

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
		if (nums.length * k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        int cnt = 0;
        List<Integer> deQueue = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
    
           while (deQueue.size() > 0 && nums[i] > deQueue.get(deQueue.size() - 1)) {
    		//将教大的值放在合适的位置
               deQueue.remove(deQueue.size() - 1);
           }
           deQueue.add(nums[i]);
           if (i >= k && nums[i - k] == deQueue.get(0)) {
    	//如果当前的队列中的元素有k个，则将队头元素出队，因为下一个窗口不会再包含这个元素了，且 //这能实现是因为前面已经提到队列中的元素存放的是按照递减的顺序的。
               deQueue.remove(0);
           }
           if (i >= k - 1) {
    	//从i = k - 1开始，添加队头元素到结果中
               result[cnt++] = deQueue.get(0);
           }

        }
        return result;
    }
}

程序运行结果：

执行用时：96ms 超过16%的java提交记录

内存消耗：53.7MB，超过6%的java提交记录

 
上面运行结果不是很理想，原因应该是在使用队列的时候需要对int和Integer进行装箱和封箱操作，其实我们完全可以根据上面的思路，使用一个数组来模拟队列的动作，只要多设置队头和队尾指针即可。代码如下：

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        if (nums.length * k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        int[] deQueue = new int[nums.length + 1];		//用数组来模拟一个双端队列
        int cnt = 0, front = 0, rear = 0;
        for (int i = 0; i < nums.length; i++) {
    
            while (front != rear && nums[i] > deQueue[rear - 1]) {
    
                rear--;	//队尾元素出队
            }
            deQueue[rear++] = nums[i];
            if (i >= k && nums[i - k] == deQueue[front]) {
    
                front++;	//队头元素出队
            }
            if (i >= k - 1) {
    	//取得队头元素
                result[cnt++] = deQueue[front];
            }
        }
        return result;
    }
}

可以看到程序的整体框架几乎是一模一样的，但是快了很多：

执行用时：10ms 打败88%的java提交记录

内存消耗：59.9MB