题解 | #滑动窗口的最大值#

#include <algorithm>
#include <vector>
class Solution {
public:
    vector<int> maxInWindows(vector<int>& num, int size) 
    {
        vector<int> vt_res;
        if (size > num.size() || size == 0)
        {
            return vt_res;
        }

        vt_res.resize(num.size() - size + 1,0);

        vector<int> vt_win(size, 0);

        //第一个窗口
        for (int i = 0; i < size; i++)
        {
            vt_win[i] = num[i];
        }
        sort(vt_win.begin(), vt_win.end());
        vt_res[0] = vt_win[size - 1];

        //窗口第一个值对应在num里的下标
        int win_first = 0;

        //遍历完其他窗口
        for (int i = size; i < num.size(); i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (num[win_first] == vt_win[j])
                {
                    /*在vt_win窗口里去掉上个窗口的第一个值，并且加入下一个窗口的最后一个值，同等与窗口移动了一样，并且整个窗口的有序状态没有大幅度破坏，后面排序的时间复杂度低*/
                    vt_win[j] = num[i];
                    win_first++;
                    break;
                }
            }

            sort(vt_win.begin(), vt_win.end());
            vt_res[i - size + 1] = vt_win[size - 1];
        }

        return vt_res;
    }
};