1. 题意

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧

移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。

滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

2. 题解

2.1 优先队列

一般最大(小)值都可以尝试用一下优先队列来做一下，刚开始没想到，

看题解有这种做法，因此来补一下。由于不仅仅需要维护值，还需要

注意下标有没有出窗口，因此我们需要维护一个$pair$，值和元素的

下标。

• 自定义比较规则

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        

        int n = nums.size();
        vector<int> ans;

        auto cmp = [](const pair<int,int> &a, const pair<int,int> &b) {
            if (a.second != b.second)
                return a.second < b.second;
            return a.first < b.first;
        };

        priority_queue< pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);



        for (int i = 0; i < n; ++i) {
             
            pq.emplace( i, nums[i] );
            
            while (pq.top().first <= i - k) {
                pq.pop();
            }

            if (i >= k - 1)
                ans.push_back( pq.top().second );
        }
    
        return ans;
    }
};

• 使用pair默认的比较规则

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        

        int n = nums.size();
        vector<int> ans;

        priority_queue<pair<int,int>> q;
        
        for (int i = 0;i < n; ++i) {

            q.emplace( nums[i], i);

            while  ( i >= k && !q.empty() && q.top().second <= i - k) {
                q.pop();
            }


            if ( i >= k - 1) {
                ans.push_back( q.top().first );
            }
        }


        return ans;
    }
};

时间复杂度$O(n{\log }_{2}n)$

空间复杂度$O(n)$

2.2 单调队列

对于新加入的元素，如果它的前面有小于等于它的元素，显然会被它

屏蔽掉。因此队列中在它前面的只有比它大的元素，因此这个队列满足

单调性，是一个单调递减队列。

相当于公司招聘程序员，新来的比老员工好用就裁掉老员工。就算老员

工能力强，超过了35岁也裁掉。

由于需要从尾部添加和删除元素，因此选择$deque$这种数据结构。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();


        // 10 2 3 4 5 

        vector<int> ans;
        
        deque<int> q;
        int hd = -1;
        int tl = 0;
         
        for (int i = 0; i < n; ++i) {
            
            if ( i >= k && (!q.empty() && q.front() == i - k)) {
                q.pop_front();
            }

            while (!q.empty() && nums[ q.back()] <= nums[i] ) {
                q.pop_back();
            }
            q.push_back( i );

            if (i >= k - 1) {
                ans.push_back( nums[q.front()]);
            }
        }

        return ans;
    }
};

时间复杂度$O(n)$

空间复杂度$O(k)$

2.3 分块+预处理

可以将数组每$k$个分成一块，求出这$k$个元素的前后缀。

对于任意一个长度为$k$的子串，必然可以由

$suf[i]$与$pre[i+k-1]$组成。

当然你也可以划分成$suf[i-(k-1)]$和$pre[i]$，

只是需要注意下下标。

这种分块预处理的方法还是很巧妙的。

我们直接预处理整个数组，$pre[i]$表示的是$i-i\%k$到$i$的最大值；

$suf[i]$表示的是$i$到$\lceil i/k\rceil k-1$的最大值。

在处理时$i\%k==0$时，$pre[i]=nums[i]$，

$(i+1)\%k==0$时，$suf[i]=nums[i]$。

注意在$i=n-1$时，$suf[i]=nums[i]$。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        

        int n = nums.size();
        vector<int> ans;

        vector<int> pre(n);
        vector<int> suf(n);

        for (int i = 0;i < n; ++i) {
            if ( i % k == 0)
                pre[i] = nums[i];
            else
                pre[i] = max( pre[i - 1], nums[i]);
        }

        for (int i = n - 1; ~i; --i) {
            if (i % k == k - 1 || i == n - 1) {
                suf[i] = nums[i];
            }
            else {
                suf[i] = max(suf[i + 1], nums[i]);
            }
        }

        // pre[i]: pre[i % k]

        // for (int i = 0; i <= n - k; ++i) {
        //     ans.push_back( max(suf[i], pre[i + k - 1]) );
        //     // why not pre[i] suf[i - (k - 1)]
        // }

        for (int i = k - 1; i < n; ++i) {
            ans.push_back( max(pre[i], suf[i - (k - 1)]));
        }

        return ans;
    }
};

时间复杂度$O(n)$

空间复杂度$O(n)$

当然上面的做法是官解，我自己的做法用的是麻烦的

滚动数组的做法，调起来是真的麻烦。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        

        int n = nums.size();
        vector<int> ans;


        vector< vector<int> > pre(2, vector<int>( k + 1, INT_MIN) );
        vector< vector<int> > suf(2, vector<int>( k + 1, INT_MIN) );

        int cur = 0;
        

        for (int i = 1;i <= k && i <= n; ++i) {
            pre[cur][i] = max( pre[cur][i - 1], nums[i - 1]);
            int suf_idx = n < k ? n - i : k - i;
            suf[cur][i] = max( suf[cur][i - 1], nums[ suf_idx ]);
        }

        ans.push_back( pre[cur][n < k ? n : k]);


        for (int s = k; s < n; s += k) {
            cur ^= 1;
            for (int j = 1; j <= k && (s + j) <= n; ++j) {
                pre[cur][j] = max( pre[cur][j - 1], nums[s + j - 1]);
                int suf_idx = s + k - j  < n ?  s + k - j : n - j;
                suf[cur][j] = max( suf[cur][j - 1], nums[ suf_idx ]);
                
                if (j == k) {
                    ans.push_back( pre[cur][k]);
                }
                else {
                    ans.push_back( max(suf[cur ^ 1][k - j], pre[cur][j]) );
                }
            }

            fill( pre[cur ^ 1].begin(), pre[cur ^ 1].end(), INT_MIN);
            fill( suf[cur ^ 1].begin(), suf[cur ^ 1].end(), INT_MIN);
            // memset(&pre[cur ^ 1], INT_MIN, sizeof(pre[cur ^ 1]));
            // memset(&suf[cur ^ 1], INT_MIN, sizeof(suf[cur ^ 1]));
        }
        return ans;
    }
};

时间复杂度$O(n)$

空间复杂度$O(k)$

3. 参考

leetcode

0x3f