239. Sliding Window Maximum

decreasing deque O(n) time O(k) space
维护一个递减deque，因为每次新数都是从尾入队列，所以能保证deque内所有数在原数组的位置都是递增的，这样就构造了一个数值递减下标递增的数据结构，每次只要检查最前面的数的位置是否已经超过了k个即可

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (!q.empty() && nums[q.back()] < nums[i]) {
                q.pop_back();
            }
            q.push_back(i);
            if (i - q.front() >= k) {
                q.pop_front();
            }
            if (i >= k - 1) {
                res.push_back(nums[q.front()]);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (k <= 0) return {};
        nums.push_back(INT_MIN);
        int n = nums.size();
        for (int i = 0; i < k; ++i) {
            enqueue(nums[i]);
        }
        vector<int> res;
        for (int i = k; i < n; ++i) {
            res.push_back(q.front());
            dequeue(nums[i - k]);
            enqueue(nums[i]);
        }
        return res;
    }

    void enqueue(int num) {
        while (!q.empty() && num > q.back()) {
            q.pop_back();
        }
        q.push_back(num);
    }

    void dequeue(int num) {
        if (q.front() == num) {
            q.pop_front();
        }
    }

    deque<int> q;
};