题目

给定一个整数数组 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	3
1 [3 -1 -3] 5 3 6 7	3
1 3 [-1 -3 5] 3 6 7	5
1 3 -1 [-3 5 3] 6 7	5
1 3 -1 -3 [5 3 6] 7	6
1 3 -1 -3 5 [3 6 7]	7

---

示例 2

输入：
nums = [1], k = 1

输出：
[1]

---

数据范围

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

实现

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // former and also smaller number is useless
        // maintian a decrease deque
        // the left end of the queue is answer
        deque<int> q;
        vector<int> res;
        for(int i = 0 ; i < nums.size() ; i ++)
        {
            // 弹出元素,直到队尾严格大于当前元素 更远的相同元素也应该被替换
            while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            // 如果队头越界,弹出
            if(q.size() && q.front() < i - k + 1) q.pop_front();

            // 元素入队,当前队头尾为最大元素
            q.push_back(i);

            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};