[//]: # 时间复杂度o(n*klogk) 当联系库函数了

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> res;
        // 队列从队尾添加元素 从队头出元素
        deque<int> q; //q记录nums下标
        for(int i = 0 ; i < nums.size() ; i++){
            // 如果该i - 队头元素下标 >= k ，证明队头元素不在这个窗口大小里面了，该退休了
            if(!q.empty() && i - q.front() >= k){
                q.pop_front();
            }
            // 维护一个从队头到队尾是递减的单调队列
            while(!q.empty() && nums[q.back()] < nums[i]){ 
                q.pop_back();
            }

            q.push_back(i);

            if(i >= k - 1){
                //返回队头元素 其是最大的
                res.push_back(nums[q.front()]);
            }
        }
        return res;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    //时间复杂度o(n*klogk)
    vector<int> maxInWindows(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        for(int i = 0 , j = k - 1; j < nums.size()  ; i++,j++){
            vector<int> copy(k);
            copy.assign(nums.begin() + i , nums.begin() + j + 1);
            sort(copy.begin() , copy.end());
            res.push_back(copy.back());
        }
        return res;
    }
};