大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列**面试题 59 – I. 滑动窗口的最大值 **。

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例:

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

解释:

提示:

  • 你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

滑动窗口这个词包含两个概念,一个是滑动,一个是窗口

首先是窗口需要生成,一开始里面是没有任何元素的。

然后再滑动,随着窗口不断的滑动,窗口里面的元素个数从 0 到 1,再到 2,再到 3,此时,从窗口里面宣传最大值。

想要找出当前窗口里面的最大值,自然而然的想法就是遍历窗口中的所有元素,从中选出最大值,这样的复杂度是 O(k*n) 级别,复杂度有点高。

剑指 Offer 59. 队列的最大值 一文中,我们提到一个概念,要想压缩时间得增大空间,即 “空间换时间” ,那么我们可以思考增大什么样的空间去压缩哪些地方的时间。

首先滑动窗口滑过所有的元素必然要经历 O(n) 的时间,这没法调整,所以可以优化的方向在于获取当前窗口的最大值,即想办法从 O(k) 优化到 O(logk)或者直接优化到 O(1)

使用双端队列

让窗口移动的过程,维护好队列里面的元素,做到每次窗口移动后都能马上知道当前窗口的最大值,由于想要做到 O(1) 的级别拿到最大值,那么必须是它的队首始终是最大值,也就是说我们需要维护一个递减队列用来保存队列中 所有递减的元素

一开始,窗口中只有 1,队列中放入 1。

窗口滑动,包含了 1 和 3,3 大于 1,如果直接放入队列,队列为 1 3,不是递减队列,所以需要先将 1 移除再放入 3 。

继续滑动,窗口元素为 1 3 -1 。

滑动窗口已经有三个元素,是合格的窗口,获取它的最大值只需要获取队列的队首元素就行。

同样的,窗口不断的向右移动,每次窗口都会增加新的元素,为了让队列中的队首元素始终是当前窗口的最大值,需要把队列中所有小于新元素值的那些元素移除。

2、规律

3、匹配

滑动窗口对应的数据结构是双端队列

4、边界

  • 窗口还未形成
  • 窗口滑动到尾部
  • 数组为空

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 Offer 59 - I. 滑动窗口的最大值.002

剑指 Offer 59 - I. 滑动窗口的最大值.003

剑指 Offer 59 - I. 滑动窗口的最大值.004

剑指 Offer 59 - I. 滑动窗口的最大值.005

剑指 Offer 59 - I. 滑动窗口的最大值.006

剑指 Offer 59 - I. 滑动窗口的最大值.007

剑指 Offer 59 - I. 滑动窗口的最大值.008

剑指 Offer 59 - I. 滑动窗口的最大值.009

剑指 Offer 59 - I. 滑动窗口的最大值.010

剑指 Offer 59 - I. 滑动窗口的最大值.011

剑指 Offer 59 - I. 滑动窗口的最大值.012

剑指 Offer 59 - I. 滑动窗口的最大值.013

剑指 Offer 59 - I. 滑动窗口的最大值.014

剑指 Offer 59 - I. 滑动窗口的最大值.015

剑指 Offer 59 - I. 滑动窗口的最大值.016

剑指 Offer 59 - I. 滑动窗口的最大值.017

剑指 Offer 59 - I. 滑动窗口的最大值.018

剑指 Offer 59 - I. 滑动窗口的最大值.019

剑指 Offer 59 - I. 滑动窗口的最大值.020

剑指 Offer 59 - I. 滑动窗口的最大值.021

剑指 Offer 59 - I. 滑动窗口的最大值.022

剑指 Offer 59 - I. 滑动窗口的最大值.023

剑指 Offer 59 - I. 滑动窗口的最大值.024

剑指 Offer 59 - I. 滑动窗口的最大值.025

剑指 Offer 59 - I. 滑动窗口的最大值.026

剑指 Offer 59 - I. 滑动窗口的最大值.027

剑指 Offer 59 - I. 滑动窗口的最大值.028

剑指 Offer 59 - I. 滑动窗口的最大值.029

剑指 Offer 59 - I. 滑动窗口的最大值.030

剑指 Offer 59 - I. 滑动窗口的最大值.031

剑指 Offer 59 - I. 滑动窗口的最大值.032

剑指 Offer 59 - I. 滑动窗口的最大值.033

剑指 Offer 59 - I. 滑动窗口的最大值.034

剑指 Offer 59 - I. 滑动窗口的最大值.035

剑指 Offer 59 - I. 滑动窗口的最大值.036

剑指 Offer 59 - I. 滑动窗口的最大值.037

剑指 Offer 59 - I. 滑动窗口的最大值.038

剑指 Offer 59 - I. 滑动窗口的最大值.039

剑指 Offer 59 - I. 滑动窗口的最大值.040

剑指 Offer 59 - I. 滑动窗口的最大值.041

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 边界情况
        if(nums.length == 0 || k == 0){
            return new int[0];
        }
        // 构建双端队列
        Deque<Integer> deque = new LinkedList<>();
        // 构建存储最大值的数组
        int[] res = new int[nums.length - k + 1];
        // 一开始滑动窗口不包含 K 个元素,不是合格的滑动窗口
        for(int i = 0; i < k; i++) {
            // 在滑动过程中,维护好 deque,确保它是单调递减队列

            // 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }

            // 考察元素可以放入到队列中
            deque.addLast(nums[i]);
        }
        // 这个时候,滑动窗口刚刚好有 k 个元素,是合格的滑动窗口,那么最大值就是队列中的队首元素
        res[0] = deque.peekFirst();


        // 现在让滑动窗口滑动
        for(int i = k; i < nums.length; i++) {
            // 滑动窗口已经装满了元素,向右移动会把窗口最左边的元素抛弃
            // i - k 为滑动窗口的最左边
            // 如果队列的队首元素和窗口最左边的元素相等,需要将队首元素抛出
            // 如果不写这个判断,会导致队列中会包含非当前窗口的元素
            // 比如窗口大小为 1,队列为 1 -1,此时窗口为 【 1 】,队列为 1,输出最大值 1,下一个窗口为 【 -1 】,准备移动的时候队列 1 和数组最左端元素一样,必须移除,否则队列中是 【 1,-1 】,输出的结果是 1,而 1 不在窗口 【 -1 】中
            if(deque.peekFirst() == nums[i - k]){
                deque.removeFirst();
            }


            // 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }

            // 考察元素可以放入到队列中
            deque.addLast(nums[i]);
            // 此时,结果数组的值就是队列的队首元素
            res[i - k + 1] = deque.peekFirst();
        }

        // 最后返回 res
        return res;
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(n)。

空间复杂度

空间复杂度为 O(k)。

七、相关标签

  • 队列
  • 滑动窗口

发表评论

邮箱地址不会被公开。 必填项已用*标注