企业官网建设流程全解析

🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

<<Git>><<MySQL>>

🌟心向往之行必能至

核心思路：单调队列

我们可以用一个 ** 双端队列（deque）** 来维护一个单调递减的序列，让队列的头部始终是当前窗口的最大值。这样，每个元素最多入队和出队一次，整体时间复杂度可以优化到O(n)。

具体步骤如下：

1. 入队维护单调性：当新元素进入窗口时，从队列尾部开始，把所有小于等于它的元素都弹出，再将它入队。这样能保证队列从队头到队尾是单调递减的。
2. 出队维护窗口边界：检查队列头部的元素下标是否已经不在当前窗口范围内，如果是，就将其弹出。
3. 记录结果：当窗口形成（即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个元素。