一、题目描述

题目大意:给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值,窗口大于数组长度的时候,返回空。

二、算法一:暴力

算法思路

  1. 如果num数组为空,或者num数组长度小于窗口长度,或者窗口长度非正,这些情况都没有区间最大值,则直接返回一个空的vector
  2. 当然,你可以直接写vector<int>(),但是常数很大,很耗费时间,所以我们在代码前面定义一个ans,此时直接返回
  3. 遍历num数组,依次计算以i为左端的窗口的最大值,边界条件是窗口右端<num.size(),因为窗口右端==窗口左端+长度-1所以有边界条件i+k-1<num.size()
  4. 内存循环定义一个mx,来记录窗口最大值,初值使他小于所有数,以至于第一次他必然被更新,即mx=INT_MIN
  5. 每次内存循环完毕,则将mx放入vector数组ans中,最后返回ans即可

代码实现

class Solution
{
public:
    vector<int> maxInWindows(const vector<int> &num, unsigned int size)
    {
        vector<int> ans;
        int len = num.size();
        int k = size;
        if (!len || len < k || k < 1)
            return ans;//返回一个空的vec,虽然写vector<int>()也行,但是常数很大,运行时间会明显增加,
            //所以此处直接返回ans,这也是ans定义在前面的原因
        for(int i=0;i+k-1<len;i++){//以i为窗口左端,所以i+k-1<len
            int mx=INT_MIN;//将区间最大值赋值为int最小值,确保任何数都比他大
            for(int j=0;j<k;j++){//寻找当前窗口最大值
                mx=max(num[i+j],mx);
            }
            ans.push_back(mx);
        }
        return ans;
    }
};

时间复杂度:O(n*k),比较离谱的是,这个算法能过原题……可以说原题的数据真的弱的离谱

三、算法二:单调队列

算法思路

  1. 总体思想:单调队列思想
  2. 我们仔细观察数组{0,1,2,3,4,5,6,6,5},我们观察num[3]=3,num[4]=4,如果当4进入窗口以后,3还有希望成为最大值吗?答案显然是不可能,为什么呢?
  3. 因为4比3晚进入,所以也比3晚出窗口,做一个比喻,接下来3的有生之年,是不是必然有4相伴?(这边针对k>=2的情况)
  4. 当然如果3出队了,那么最大值也肯定没有他的事情了,所以只要4进入了,那么3就再也没有机会成为最大值了
  5. 我们再接着看,如果k大一点,是不是4进入窗口后,num[2]=2也没有回成为最大值了?这样我们是不是只要维护k个数字的队列,记录这个数是不是比前面的数大,如果是就从队尾删除掉前面的数,这样不就省去了很多的比较过程吗?
  6. 那如果比前面的数小呢?此时我们依旧放入队尾,因为当前面的数不在窗口中时,我们当前的数就有可能成为最大值了
  7. 如何保证我们维护的范围始终是在这个窗口内呢?因为先进入的数,必然比后进去的数来的小,所以先进入的数会更早的出队,这个时候我们就需要判断队首是否过期了。
  8. 如果队首<窗口左端那么就说明队首过期了,我们需要出队,而窗口左端==窗口右端-长度+1,即i-k+1
  9. 最后还需要解决的一个问题就是,我们需要一个支持队尾队首都可以出队的数据结构?没错,双端队列。不过我们记录的得是下标,因为只有记录下标,我们才既能判断队首是否过期,也能访问具体的值
  10. 时间复杂度O(n),num中每个数仅入队一次出队一次,空间复杂度为O(k),因为我们开了一deque,且过程中因为窗口大小的限制,deque的size最大为k,(数据递增的时候取到)

动画演示

图片说明

代码实现

class Solution
{
public:
    vector<int> maxInWindows(const vector<int> &num, unsigned int size)
    {
        vector<int> ans;
        int len = num.size();
        int k = size;
        if (!len || len < k || k < 1)
            return ans;//返回一个空的vec,虽然写vector<int>()也行,但是常数很大,运行时间会明显增加,
            //所以此处直接返回ans,这也是ans定义在前面的原因,不和deque一起定义的原因
        deque<int> q;
        for (int i = 0; i < len; i++)
        {
            while (!q.empty() && num[q.back()] < num[i])//单调队列的尾,永远不可能成为最大值了,此时就出队
            {
                q.pop_back();
            }
            q.push_back(i);//i入队
            //放在push_back后可以省略去判断单调队列是否非空,小优化时间复杂度
            if (q.front() < i - k + 1) //单调队列的头已经过期,即超过以i为最右端的窗口的范围,窗口右端-长度+1==窗口左端
            {
                q.pop_front();//头部出队
            }
            if (i >= k - 1) //vector下标从0开始,所以i>=k-1时才可以构成窗口
            {
                ans.push_back(num[q.front()]);//单调队列的头,在num中对应的元素(下标),即为当前窗口的答案
            }
        }
        return ans;
    }
};