暴力

时间复杂度 O(n*k),空间复杂度O(1)

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> result;
        int len = num.size();
        if (len == 0 || size < 1 || len < size) return result;
        for (int i = 0; i + size - 1 < len; ++i) {
            int j = i + size - 1;
            int max_val = num[j];
            for (int k = j; k >= i; --k) {
                max_val = max(num[k], max_val);
            }
            result.push_back(max_val);
        }
        return result;
    }
};

单调队列

时间复杂度 O(n),空间复杂度O(k)

#include <deque>
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> result;
        int len = num.size();
        if (len == 0 || size < 1 || len < size) return result;
        
        deque<int> dq_idx;
        // 初始窗口
        for (int i = 0; i < size; ++i) {
            while (!dq_idx.empty() && num[i] >= num[dq_idx.back()]) {
                dq_idx.pop_back();
            }
            dq_idx.push_back(i);
        }
        
        for (int i = size; i < len; ++i) {
            result.push_back(num[dq_idx.front()]);
            // 如果当前元素大，则要从后面把比num[i]小的都pop
            while (!dq_idx.empty() && num[i] >= num[dq_idx.back()]) {
                dq_idx.pop_back();
            }
            // 将队头过期元素清除
            while (!dq_idx.empty() && i - dq_idx.front() >= size) {
                dq_idx.pop_front();
            }
            dq_idx.push_back(i);
        }
        result.push_back(num[dq_idx.front()]);
        return result;
    }
};