下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 12 | 面试题:返回滑动窗口中的最大值
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享

精选留言(58)

  • 2018-10-15
    看一个数组:1,3,1,2,0,5 window也设为3。会移动到这步:deque:[3,1,2],再下一步变为:[1,2,0] 此时deque中第一个元素(也就是最大元素)是1而不是2!

    作者回复: 2进入window的时候,会把前面的那个1先顶出window.

    16
  • 2019-04-26
    看前面很多人评论的问题,其实老师白班讲解由[3,-1,-3],5变成3,[-1,-3,5]的时候,出队顺序会让人误解,其实应该是维护队列需要从两边出队,也就是先把3从左边出队,然后判断-3<5,把-3从右边出队,再把-1出队,最后把5从右边入队

    作者回复: 对的。

    14
  • 2018-10-21
    和 子青 同学同样的问题
     [1,3,1,2,0,5] k=3, 第一次队列元素为[3,1]返回3,第二次为[3,1,2],返回3,第三次[1,2,0] 返回1,而不是2。 老师说的2入队列的时候会把1挤出去,是怎么做到的呢?难道每次将新增元素与队列所有元素进行比较吗?
    2
    8
  • 2019-01-13
    请问maxheap的方法中,window向右移时,最左元素如何去除的呢?heap不是只能去除顶点吗?
    4
    6
  • 2019-02-26
    Java 版本答案
    public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0) return new int[0];
            
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> deque = new ArrayDeque<>();
            
            for(int i=0;i<nums.length;i++) {
                // 删除队列中小于窗口左边下标的元素
                if(i >= k && i - k + 1 > deque.peek()) deque.remove();
                
                // 从队列右侧开始, 删除小于nums[i] 的元素
                while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
                    deque.removeLast();
                
                deque.add(i);
                
                // 队列左侧是最大值,加入结果
                if(i - k + 1 >= 0)
                    res[i - k + 1] = nums[deque.peek()];
            }
            return res;
        }
    展开

    作者回复: 帅!!

    3
    4
  • 2019-01-24
    看了半天终于明白了,这个题目的关键在于队列里面存储的是下标而不是元素值,这样可以解决窗口滑动的问题. 写了一个java版本的实现.
    public static ArrayList<Integer> kSlidingMax2(int k,int []a){
            ArrayList<Integer> result = new ArrayList<>();
            Queue<Integer> queue = new LinkedBlockingQueue<>(k);
            queue.add(0); //将数据第一个元素先放入队列.
            for(int i=1;i<a.length;i++){
                //判断最大元素是否超出滑动窗口,若超出则将最大元素移出队列.
                //可以保证队列内的元素始终小于等于k个. 这个才是整个算法的关键
                //注意队列里面放的是元素的下表而不是元素的值.
                if(queue.peek()<i-k+1){
                    queue.remove();
                }
                //新的元素要a[i]要入队,入队之前先清除比a[x]小的元素
                Iterator<Integer> it = queue.iterator();
                while (it.hasNext()){
                    if(a[it.next()]<a[i]){
                        it.remove();
                    }
                }
                queue.add(i);

                if(i>=k-1){
                    result.add(a[queue.peek()]);
                }
            }
            return result;
        }
    展开
    4
  • 2019-01-18
    懂了,队列的元素已经按照从大到小自然排列了,所以每个入队的元素只有被后来者比较一次的机会,所以内循环可以不算做时间复杂度n
    3
  • 2019-01-06
    我在写此类算法题时候,使用的是JS语言, 所以直接编写如下的代码:
    var maxSlidingWindow = function(nums, k) {
      if (nums.length === 0) return nums;
      const r = [];
      for (let i = k; i <= nums.length; i++) {
        r.push(Math.max(...nums.slice(i - k, i)));
      }
      return r;
    };
    我当时还特别疑惑为什么此题的难度为hard。

    编程语言有时候会限制个人的思维, 前端的代码没有遇到过复杂的数据结构, 导致一些思路根本打不开,这也是我需要克服的一点。
    展开

    作者回复: 好的总结和回顾! 👍🏻

    3
  • 2018-10-19
    使用双端队列实现的时候双端队列里存储的 数组索引,而不是元素,这样才能实现 O(n) 的时间复杂度
    3
  • 我的理解一种算法比另外种在当前环境下更优一定是有地方解决了前一种算法的哪里做的无用功,这个例子里deque是不是就是避免了堆中需要重排的这部分无用功从而优化了性能?有一点不理解的地方为什么用deque,我看并没有从右边出列的情况,使用普通的队列为什么不行呢?

    作者回复: 这是一个很好的问题。首先为什么用deque,就是因为在插入的时候,需要从 window 左边移除元素,而下标出了 window 之后,需要用右侧移除。回到你前半部分的理解:算法更优是因为有地方解决了前一种算法做的无用功,这个正确:这里我们不需要用堆去维护window里k个元素的大小顺序,只需要记录最大值,所以用heap有点杀鸡用牛刀的意思。

    2
  • 2018-10-18
    老师,有一种情况,
    [6,4,5,3,2,1],k=3,
    当3入队时,6出队,因为4和5都比3大,所以需要重新判断窗口中哪个数值最大,这部分的时间复杂度是不是忘记算了?

    作者回复: 4在5被加入的时候就已经出去。由于每个元素只在window里呆一次,所以操作window的复杂度不和循环进行嵌套了。

    2
  • 2018-10-13
    deque没有维护第二大数字,当最大值移除后,是否要重新算最大值?

    作者回复: 对的,需要的。只是按照我们开始的算法,最大数出去之后,剩下的第二个数就是window-k里的最大数。

    2
  • 2018-10-11
    每个元素进队列后,是需要判断是否要干掉前面的数的吧,这个时间不用算吗?

    作者回复: 这个判断的时间是常数时间,不会在里面嵌套O(n)的时间,因为在全部循环操作中,每个元素都只进入k window一次

    1
    2
  • 在MaxHeap的方法裡面講到當窗口移動的時候,要把移動後被去除的元素從Heap中移除。在老師的例子中,原本 [1, 3, -1] 滑動後 [3, -1, -3],必須要把1從Heap中移除。但是問題就在這裡,1並不是Heap的頭元素,所以必須要用搜索遍歷整個Heap,找到元素所在位置並刪除。這種情況下最後的時間複雜度就不會是N*logK。
    3
    1
  • 2019-06-20
    老师的思路我懂了后,仍然无法下笔。因为我感觉好多case要考虑。

    然后看了一下大家的评论也没有我想得到的。我最困惑的的是这么复杂的过程,怎么实现?

    1.思路:what
    使用一个容器(容量k)保存最大的,以及最大后面的。最大之前的值,在之后寻找最大值过程中都用不上。
    按理说只需要保存一个最大值。但是最大之后的小值也需要保存,作用是之后用来判断容器是否满了(达到k个)。

    2.实现:how
    这里面到底要考虑几种case啊?答案是两种。
    以最大值进来时是否在最左边为依据来实现代码。

    一种,最大值在k个的最左边,这样下一次进来一个值之前需要先删除最左边的。

    另一种,最大值不在最左边,有足够的空间给下次进来。此时需要删除最大值左边的,让最大值始终在最左边。

    3.为什么这个是o(n)?为啥要双端?why

    整个思路过程中的运算时间复杂度都在2里面删除操作和进入操作和比较操作。
    自己模拟一下,会发现所有的删除操作加起来为o(n)。
    进入操作就是一次遍历o(n)。
    比较操作也是一次遍历o(n)。


    为啥要双端?
    对于3,-1,1的情况,如果进来一个2,那就需要从右边出来了。
    展开
    1
  • 2019-01-27
    新元素进入window要从右侧元素开始比较,不能从左侧比较。
     var maxSlidingWindow = function (nums, k) {
          const window = [];
          const result = [];
          for (let i = 0; i < nums.length; i++) {
            if (i - window[0] > k - 1) {
              window.shift();
            }
            let j = window.length - 1;
            while (j >= 0 && nums[window[j]] <= nums[i]) {
              j--;
              window.pop();
            }
            window.push(i);
            if (i >= k - 1) {
              result.push(nums[window[0]]);
            }
          }
          return result;
        };
    展开
    1
  • 2019-01-27
    第二个解法有问题,[1,3,1,2,0,5]这种case过不了
    1
  • 2019-12-05
    速度超越100%php的答案

    class Solution
    {
        /**
         * @param Integer[] $nums
         * @param Integer $k
         * @return Integer[]
         */
        public function maxSlidingWindow($nums, $k)
        {
            list($max, $maxPos) = $this->getMaxAndMaxPos($nums, 0, $k);

            $return = [$max];
            for ($i = 1; $i <= count($nums) - $k; $i++) {
                if ($i <= $maxPos) {
                    if ($max < $nums[$i + $k - 1]) {
                        list($max, $maxPos) = [$nums[$i + $k - 1], $i];
                    }
                } else {
                    list($max, $maxPos) = $this->getMaxAndMaxPos($nums, $i, $k);
                }
                $return[] = $max;
            }
            return $return;
        }

        protected function getMaxAndMaxPos($nums, $offset, $len)
        {
            for ($i = $offset, $max = $nums[$offset], $maxPos = $offset; $i < $offset + $len; $i++) {
                if ($nums[$i] > $max) {
                    list($max, $maxPos) = [$nums[$i], $i];
                }
            }
            return [$max, $maxPos];
        }
    }
    展开
  • 2019-10-17
    PHP 实现:
    function maxSlidingWindow($nums, $k) {
           if (empty($nums)) return $nums;
            $res = [];
            $window = [];
            foreach ($nums as $key => $num) {
                if ($key >= $k && $window[0] <= $key - $k) {
                    array_shift($window);
                }

                while ($window && $nums[end($window)] < $num){
                    array_pop($window);
                }


                $window[] = $key;
                if($key >= $k-1){
                    $res[] = $nums[$window[0]];
                }
            }
             return $res;
        }
    展开
  • 2019-07-27
    老师,请问你的T恤 在哪里买的啊,好酷啊,特别想入手一件,哈哈哈!

    作者回复: 是我们公司的衣服。