leetcode 239. Sliding Window Maximum 滑动窗口最大值Maximum + 优先级队列 + multiset + Heap

不念不忘少年蓝@ 2022-06-08 12:48 131阅读 0赞

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,  
Given nums = \[1,3,-1,-3,5,3,6,7\], and k = 3.

Window position                Max
    ---------------               -----
     [1  3  -1] -3  5  3  6  7       3
      1 [3  -1  -3] 5  3  6  7       3
      1  3 [-1  -3  5] 3  6  7       5
      1  3  -1 [-3  5  3] 6  7       5
      1  3  -1  -3 [5  3  6] 7       6
      1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as \[3,3,5,5,6,7\].

Note:  
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

这道题就是考察滑动窗口的Maximum，最直接的方法就是暴力，然后在Java中可以考虑使用优先级队列，但是这个还是不符合题意的时间复杂度的要求。

使用最大堆或者二叉搜索树是做好的做法，所以我赞成C++的做法，很不错

网上看到了使用双向队列完成的做法，很棒，总之就是这样做的，就是尾部压进元素，头部到尾部是从大到小的排列，每一次的压入相当于插入排序，然后得到元素即可。

代码如下：

import java.util.Collections;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.PriorityQueue;
    
    /*
     * 使用双向队列很棒，首先这里保存的是index，而不是具体的值
     * 因为我们在滑动窗口的时候会不断添加元素，然后删除元素，同时还要记录最大值
     * 所以我们每一次添加元素都保存较大的元素，这个就是在deque的末尾添加的元素的技巧
     * 
     * 同时每当我们发现我们保存的最大元素是i-k也即，这个最大元素应该淘汰了，那么直接pop，
     * 滑动窗口并不是时钟保存窗口k个元素，而是保存着最大的元素，还可能有第二大，第三大的元素等等
     * */
    class Solution 
    {
        public int[] maxSlidingWindow(int[] nums, int k) 
        {
            if(nums==null || nums.length<0 || k<=0 || k==1)
                return nums;
    
            int []res=new int[nums.length-k+1];
            int count=0;
            Deque<Integer> deque=new LinkedList<Integer>();
            for(int i=0;i<nums.length;i++)
            {
                // 每当新数进来时，如果发现队列头部的数的下标，是窗口最左边数的下标，则扔掉
                if(deque.isEmpty()==false && deque.peekFirst()==i-k)
                    deque.pollFirst();
    
                // 把队列尾部所有比新数小的都扔掉，保证队列是降序的
                while(deque.isEmpty()==false && nums[deque.peekLast()] < nums[i])
                    deque.removeLast();
    
                // 添加新数
                deque.addLast(i);
                // 队列头部就是该窗口内第一大的
                if(i+1>=k)
                    res[count++]=nums[deque.peekFirst()];
            }
            return res;
        }
    
    
        /*
         * 使用优先级队列，是最直接的方法
         * 
         * 使用优先级队列保存窗口的k个元素，然后可以得到最大值，
         * 遍历一次即可完成，不过时间不是O(n),
         * */
        public int[] maxSlidingWindowByProQueue(int[] nums, int k) 
        {
            if(nums==null || nums.length<0 || k<=0 || k==1)
                return nums;
    
            int []res=new int[nums.length-k+1];
            int count=0;
            PriorityQueue<Integer> queue=new PriorityQueue<>(Collections.reverseOrder());
            for(int i=0;i<nums.length;i++)
            {
                if(i+1<=k)
                    queue.add(nums[i]);
                else
                {
                    queue.add(nums[i]);
                    queue.remove(nums[i-k]);
                }           
                if(queue.size()==k)
                    res[count++]=queue.peek();
            }
            return res;
        }
    }

下面是C++的做法，就是一个简单的遍历，**注意中间使用优先级队列来完成最大窗口值得判断，但是要注意的是C++的优先级队列不支持中中间删除元素，只支持队列头部尾部的添加和删除，所以这里使用multiset来做，因为和set一样内部使用的是平衡的二叉搜索树来实现**

代码如下：

#include <iostream>
    #include <alogrithm>
    #include <set>
    #include <map>
    #include <vector>
    #include <stack>
    #include <queue>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) 
        {
            vector<int> res;
            multiset<int> que;
            for (int i = 0; i < nums.size(); i++)
            {
                if (i < k)
                    que.insert(nums[i]);
                else
                {
                    que.insert(nums[i]);
                    que.erase(que.find(nums[i-k]));
                }
    
                if(que.size()==k)
                    res.push_back(*que.rbegin());
            }
            return res;
        }
    };