滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：滑动窗口的位置

[1 3 -1] -3 5 3 6 7

1 [3 -1 -3] 5 3 6 7

1 3 [-1 -3 5] 3 6 7

1 3 -1 [-3 5 3] 6 7

1 3 -1 -3 [5 3 6] 7

1 3 -1 -3 5 [3 6 7]

此题是单调队列的经典题。用 deque 自己实现一个单调队列。

单调队列必须保证队头是最大的，队尾是最小的，并且从队头弹出，从队尾入队。入队：先把比这个数小的都踢出去再入队。出队：每次只出队头的最大值，其他的禁止出队。

滑动窗口每次滑动，把旧值从单调队列中剔除，把新值加入单调队列。每次的队头是最大值。

C++43 linesExpandCollapse

class MyQueue {
public:
    deque<int> que;
    
    // 如果传入的是单调队列的队头（最大值），就弹出，否则啥也不做
    void pop(int num) {
        if (!que.empty() && que.front() == num) {
            que.pop_front();
        }
    }
    
    // 把比当前 num 小的值全踢出去再入队列
    void push(int num) {
        while (!que.empty() && que.back() < num) {
            que.pop_back();
        }
        que.push_back(num);
    }
    
    int front() {
        return que.front();
    }
};

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> ans;
    
    MyQueue q;
    // 先把前 k 个数放到队列里
    for (int i = 0; i < k; i++) {
        q.push(nums[i]);
    }
    
    ans.push_back(q.front());
    for (int i = k; i < nums.size(); i++) {
        q.pop(nums[i - k]);
        q.push(nums[i]);
        ans.push_back(q.front());
    }
    
    return ans;
    
}