滑动窗口最大值问题

秒速五厘米 2023-03-13 02:29 21阅读 0赞

## 写在前面 ##

如果觉得写的不错，有所帮助，记得点个关注和点个赞，不胜感激。  
这一次想要说的这道题，如果不加其他限制条件或者不追求时间复杂度低的算法的话，其实很容易实现。不过我貌似说的是废话，如果想要追求巧妙的算法，当然难毒药比较大，而这个问题，我学习到了巧妙的算法思路，以及双向队列的应用点。

## 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]

## 直接暴力 ##

最简单直接的方法是遍历每个滑动窗口，找到每个窗口的最大值。一共有  N − k + 1 N - k + 1 N−k\+1 个滑动窗口，每个有  k k k 个元素，于是算法的时间复杂度为  O ( N k ) O(N k) O(Nk)，表现较差。

public int[] maxSlidingWindow(int[] nums, int k) { 
        int n = nums.length;
        if (n * k == 0) return new int[0];
        
        int [] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) { 
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++) 
                max = Math.max(max, nums[j]);
            output[i] = max;
        }
        return output;
    }

## 双向队列 ##

其实这里的话，我们需要先理解双向队列，这个是一个很有用的数据结构，他可以让我们在  O ( 1 ) O(1) O(1) 的时间复杂度内，访问头部和尾部的节点。所以，我们可以使用双向队列来帮助我们，实现  O ( N ) O(N) O(N) 时间复杂度内，得到结果。  
处理前 k 个元素，初始化双向队列。

class Solution { 
      ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
      int [] nums;
    
      public void clean_deque(int i, int k) { 
      	//如果当前索引超过了K，那么就删除队列头部的元素
        if (!deq.isEmpty() && deq.getFirst() == i - k)
          deq.removeFirst();
    
    	//如果当前索引元素的值，大于队尾元素值，那么就删除队尾元素值，这一步
    	//可以保证队列内部元素值是一个降序的排列
        while (!deq.isEmpty() && nums[i] > nums[deq.getLast()]) 
        	deq.removeLast();
      }
    
      public int[] maxSlidingWindow(int[] nums, int k) { 
        int n = nums.length;
        if (n * k == 0) return new int[0];
        if (k == 1) return nums;
    
        this.nums = nums;
        int max_idx = 0;
        //先遍历前K个元素
        for (int i = 0; i < k; i++) { 
          clean_deque(i, k);
          deq.addLast(i);
          if (nums[i] > nums[max_idx]) max_idx = i;
        }
        //初始化output结果集
        int [] output = new int[n - k + 1];
        output[0] = nums[max_idx];
    
    	//开始遍历剩余元素
        for (int i  = k; i < n; i++) { 
          clean_deque(i, k);
          deq.addLast(i);
          output[i - k + 1] = nums[deq.getFirst()];
        }
        return output;
      }
    }

## 动态规划 ##

其实这道题，我自己在写的时候，也想到要用动态规划去解决，不过由于水平问题，我再找动态方程的时候，出现了一些问题，不好找。其实动态规划这个不算典型，不过将它讲成动态规划更好理解。使用这种思路的关键，在于我们构建两个记录，从左向右，以及从右向左两个方向记录，当前K个元素中，嘴个的数，然后取其中更大的一个数。  
![在这里插入图片描述][20200509193517849.png_pic_center]

*  从左到右遍历数组，建立数组 left。
 *  从右到左遍历数组，建立数组 right。
 *  建立输出数组 max(right\[i\], left\[i + k - 1\])，其中 i 取值范围为 (0, n - k + 1)。

public int[] maxSlidingWindow(int[] nums, int k) { 
        int n = nums.length;
        if (n * k == 0) return new int[0];
        if (k == 1) return nums;
    
        int [] left = new int[n];
        left[0] = nums[0];
        int [] right = new int[n];
        right[n - 1] = nums[n - 1];
        for (int i = 1; i < n; i++) { 
          // from left to right
          if (i % k == 0) left[i] = nums[i];  // block_start
          else left[i] = Math.max(left[i - 1], nums[i]);
    
          // from right to left
          int j = n - i - 1;
          if ((j + 1) % k == 0) right[j] = nums[j];  // block_end
          else right[j] = Math.max(right[j + 1], nums[j]);
        }
    
        int [] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++)
          output[i] = Math.max(left[i + k - 1], right[i]);
    
        return output;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/efe71d468f5a458399d0d8176b26194e.png
[20200509193517849.png_pic_center]: /images/20230312/40d953610fef44d0aa17788eebc42ce9.png