🔥个人主页：Milestone-里程碑
❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>
<<Git>><<MySQL>>
🌟心向往之行必能至
核心思路：单调队列
我们可以用一个 ** 双端队列（deque）** 来维护一个单调递减的序列，让队列的头部始终是当前窗口的最大值。这样，每个元素最多入队和出队一次，整体时间复杂度可以优化到O(n)。
具体步骤如下：
- 入队维护单调性：当新元素进入窗口时，从队列尾部开始，把所有小于等于它的元素都弹出，再将它入队。这样能保证队列从队头到队尾是单调递减的。
- 出队维护窗口边界：检查队列头部的元素下标是否已经不在当前窗口范围内，如果是，就将其弹出。
- 记录结果：当窗口形成（即
left >= 0）时，队列头部就是当前窗口的最大值，将其加入结果数组。
完整代码
cpp
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); vector<int> ans(n - k + 1); // 结果数组大小为窗口数量 deque<int> q; // 双端队列，存储元素下标 for (int i = 0; i < n; ++i) { // 1. 维护队列的单调递减性 while (!q.empty() && nums[q.back()] <= nums[i]) { q.pop_back(); } q.push_back(i); // 2. 移除窗口外的元素 int left = i - k + 1; // 当前窗口的左边界 if (q.front() < left) { q.pop_front(); } // 3. 当窗口形成时，记录最大值 if (left >= 0) { ans[left] = nums[q.front()]; } } return ans; } };示例验证
以题目中的示例 1 为例：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3我们的算法会依次维护队列：
- 窗口
[1,3,-1]→ 队列：[1]→ 最大值3 - 窗口
[3,-1,-3]→ 队列：[1,2]→ 最大值3 - 窗口
[-1,-3,5]→ 队列：[4]→ 最大值5 - 最终输出结果：
[3,3,5,5,6,7]，与示例完全一致。
复杂度分析
- 时间复杂度：
O(n)。每个元素最多被加入队列一次，弹出队列一次，总操作次数为2n。 - 空间复杂度：
O(k)。队列中最多存储k个元素。
