滑动窗口最大值（239）题解难度：困难

余生大大

发布于 2022-11-02 16:39:52

27600

代码可运行

文章被收录于专栏：余生大大余生大大

运行总次数：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]

提示：

1 <= nums.length <= 10^5
-10⁴ <= nums[i] <= 104⁴
1 <= k <= nums.length

解析

暴力破解

这道题如果用暴力破解的方式比较简单，但是时间复杂度比较高，先说暴力破解的方法。

窗口内的数字数量是已知的k，可以根据原始数组nums跟窗口内数字数量k得出有多少个窗口，也就是返回的数组长度，公式为：nums.length - k + 1，以示例一代入公式：8 - 3 + 1 = 6 示例一的窗口数量为6个，后面的循环次数用窗口数量即可。

窗口数量已知可能性就已知，所以第一层循环次数直接以nums.length - k + 1结果的值为判定条件，二层循环则去判定窗口内k个数值的最大值，取每个窗口的最大值写入到返回数组，这是暴力破解的方式。

代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int fnum = nums.length-k+1;
        int result[] = new int[fnum];
        for(int i = 0; i < fnum; i++){
            int max = -10001;
            for(int j = i;j < k+i; j++){
                if(nums[j] > max){
                    max = nums[j];
                }
            }
            result[i] = max;
        }
        return result;
    }
}

执行结果：

暴力破解的时间复杂度为O(n²)，空间复杂度为O(1)，这种方式的解法超出了时间限制，那就得换一种方式了。

队列最大值

既然题目要求的是获取每个窗口的最大值，在循环的时候使用队列记录窗口循环下标内最大的值，在队列中保证队列是有序的递减队列，这样获取最大值直接从队列头获取即可，如果队列尾值 < 循环值需要将队列尾值弹出，如果循环下标超出窗口位数要将队列头值弹出。

操作步骤：

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

L-R为窗口值
初始状态：L=R=0，队列：{}
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]

代码如下：

    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
        int result[] = new int[nums.length-k+1];
        for (int i = 0; i < nums.length; i++) {
            // 判断值是否比尾部值大，大的话将队列的尾部值退出
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.addLast(i);
            // 超出窗口的值退出队列
            if(deque.peek() <= i-k){
                deque.poll();
            }
            // 前面n-1不参与数组写入
            if(i+1 >= k){
                result[i+1-k] = nums[deque.peek()];
            }
        }
        return result;
    }

执行结果：

这种方法的时间复杂度为O(n)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-09-14，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度