精选留言(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
• 
  andi轩

  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
• 
  web

  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
• 
  kris37

  2018-10-19

  使用双端队列实现的时候双端队列里存储的 数组索引，而不是元素，这样才能实现 O(n) 的时间复杂度

  

   3
• 
  冰梨icePear🍐

  2018-10-22

  我的理解一种算法比另外种在当前环境下更优一定是有地方解决了前一种算法的哪里做的无用功，这个例子里deque是不是就是避免了堆中需要重排的这部分无用功从而优化了性能？有一点不理解的地方为什么用deque，我看并没有从右边出列的情况，使用普通的队列为什么不行呢？

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

  

   2
• 
  L*Z*田

  2018-10-18

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

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

  

   2
• 
  周军5656

  2018-10-13

  deque没有维护第二大数字，当最大值移除后，是否要重新算最大值?

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

  

   2
• 
  杨松宝

  2018-10-11

  每个元素进队列后，是需要判断是否要干掉前面的数的吧，这个时间不用算吗？

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

   1

   2
• 
  小琛琛还要继续努力

  2019-07-11

  在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
• 
  lzh

  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];
      }
  }

  展开

  

  
• 
  Aliliin

  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恤 在哪里买的啊，好酷啊，特别想入手一件，哈哈哈！

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

  

  