题解 | #合并两个有序的数组#

一、题目描述

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

二、算法一：暴力

算法思路

如果num数组为空，或者num数组长度小于窗口长度，或者窗口长度非正，这些情况都没有区间最大值，则直接返回一个空的vector
当然，你可以直接写vector<int>()，但是常数很大，很耗费时间，所以我们在代码前面定义一个ans，此时直接返回
遍历num数组，依次计算以i为左端的窗口的最大值，边界条件是窗口右端<num.size()，因为窗口右端==窗口左端+长度-1所以有边界条件i+k-1<num.size()
内存循环定义一个mx，来记录窗口最大值，初值使他小于所有数，以至于第一次他必然被更新，即mx=INT_MIN
每次内存循环完毕，则将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)，比较离谱的是，这个算法能过原题……可以说原题的数据真的弱的离谱

三、算法二：单调队列

算法思路

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