[剑指offer]面试题第[59-1]题[Leetcode][第239题][JAVA][滑动窗口的最大值][单调队列][优先队列]

心已赠人 2023-02-26 02:07 18阅读 0赞

#### 【问题描述】\[困难\] ####

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

#### 【解答思路】 ####

###### 1. 暴力 ######

两层 for 循环，每次都从窗口中找最大值即可  
**时间复杂度：O(N^2) 空间复杂度：O(N)**

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

###### 2. 优先队列 ######

当优先队列的数字等于窗口大小的时候，我们只需要将第一个元素删除，然后将新的数字加入。  
**时间复杂度：O(NlogN) 空间复杂度：O(1)**

public int[] maxSlidingWindow(int[] nums, int k) { 
        // 建立最大堆
        Queue<Integer> max = new PriorityQueue<Integer>(new Comparator<Integer>() { 
            @Override
            public int compare(Integer i1, Integer i2) { 
                // TODO Auto-generated method stub
                return i2 - i1;
            }
        });
        int n = nums.length;
        if (n == 0) { 
            return nums;
        }
        int result[] = new int[n - k + 1];
        int index = 0;
        for (int i = 0; i < n; i++) { 
            //移除第一个元素
            if (max.size() >= k) { 
                max.remove(nums[i - k]);
            }
            max.offer(nums[i]);
            //更新 result
            if (i >= k - 1) { 
                result[index++] = max.peek();
            }
        }
        return result;
    }

###### 2. 单调队列（单调栈思想） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(N)**

public int[] maxSlidingWindow(int[] nums, int k) { 
            int n = nums.length;
            if(n == 0)  return nums;
            int[] res = new int[n - k + 1];
    
            //dq里面存的是数组的index, 不是数组的值
            Deque<Integer> dq = new LinkedList<>();
    
            for(int i = 0; i < n; i++){ 
                //Step1: 头: 移除头部, 保证窗口的长度范围
                if(!dq.isEmpty() && dq.getFirst() < (i - k + 1)){ 
                    dq.removeFirst();//poll();
                }
                //Step2: 尾: 移除尾部小于当前值得元素, 原理参考篮球队长模型, 去除不可能的元素
                while(!dq.isEmpty() && nums[i] >= nums[dq.getLast()]){ 
                    dq.removeLast();
                }
                //Step3: 尾部加入, 滑动窗口向右扩充
                dq.addLast(i);
                //Step4: 头, 从头部返回极大值
                if(i >= k - 1){ 
                    res[i - k + 1] = nums[dq.getFirst()];
                }
            }
    
            return res; 
        }

#### 【总结】 ####

###### 1.Deque存放index ######

![在这里插入图片描述][20200713164332383.png]

###### 2. 单调Deque双端队列 ######

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2][]

###### 3.单调栈思想 ######

单调栈专门解决「找左边（或者右边）第 1 个严格大于自己的元素」  
存的是下标  
![在这里插入图片描述][20200713172913631.png]

转载链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/yi-dong-shi-pin-javaban-ben-shuang-duan-dui-lie-de/  
单调队列视频讲解链接https://www.bilibili.com/video/BV1YV411o7Gr/  
参考链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-3/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/50fe801b967e4f9a9e195cc0cad815a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200713162329241.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200713164332383.png]: https://img-blog.csdnimg.cn/20200713164332383.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020071316531489.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200713172913631.png]: https://img-blog.csdnimg.cn/20200713172913631.png