企业官网建设流程全解析

题目信息（题目链接）：

LeetCode 239. 滑动窗口最大值
题目要求：给定数组nums和窗口大小k，窗口从左向右滑动，返回每一步窗口中最大值组成的数组。

面对这道题，第一反应是暴力解法：

// 暴力解法伪代码 for (int i = 0; i <= nums.size() - k; i++) { int max_val = INT_MIN; for (int j = i; j < i + k; j++) { max_val = max(max_val, nums[j]); // 遍历窗口内 k 个元素找最大值 } result.push_back(max_val); }

时间复杂度：O(N * k)。
当数据量达到 10^5 级别时，计算量必然导致Time Limit Exceeded (TLE)。我们急需一种能在O(1)时间内获取窗口最大值的数据结构。

思路演化：单调队列

如何优化？我们发现暴力解法中，很多元素被重复比较了。
假设窗口内有两个元素nums[i]和nums[j]，且i < j（i 在 j 左边），如果nums[i] <= nums[j]，那么只要nums[j]还在窗口内，nums[i]就永远不可能成为最大值。因为nums[j]比它大，且比它晚离开窗口。

基于这个观察，我们可以维护一个单调递减的队列：

队列里存放元素的下标。

队列头部的元素永远是当前窗口的最大值。

当新元素加入时，从队尾开始，把所有小于等于新元素的旧元素统统踢出队列

当窗口滑动时，检查队首元素是否过期（滑出窗口），过期则从队首移除。

这就是单调队列的核心思想：剔除了无用元素，使得获取最大值的时间复杂度降为 O(1)。

C++std::deque相关函数解析

在 C++ 中，实现单调队列的最佳容器是std::deque（双端队列）。因为它允许我们在O(1)的时间内对两端进行操作。

结合本题，我们需要用到以下 4 个核心函数：

dq.back()：返回队尾元素的引用。

本题作用：用于比较新元素与队尾元素的大小，判断是否需要剔除队尾。

dq.pop_back()：删除队尾元素。

本题作用：当队尾元素小于等于新元素时，将其弹出，维持队列单调递减。

dq.front()：返回队首元素的引用。

本题作用：获取当前窗口最大值的下标；同时检查队首下标是否过期。

dq.pop_front()：删除队首元素。

本题作用：当队首元素滑出窗口（过期）时，将其弹出。

dq.push_back(i)：在队尾插入元素i（下标）。

本题作用：新元素入队。

代码：

下面是结合上述思路和deque函数的完整 C++ 代码，时间复杂度O(N)，空间复杂度O(k)。

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; deque<int> dq; // 存储数组下标，对应 nums 的值单调递减 for (int i = 0; i < nums.size(); i++) { // 1. 入队：维护单调递减 // 如果队尾元素 <= 当前元素，说明队尾永远无法成为最大值了，弹出 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); // 当前元素下标入队 // 2. 出队：检查队首是否过期 // 窗口左边界是 i - k，如果队首下标 <= i - k，说明已经滑出窗口 if (dq.front() <= i - k) { dq.pop_front(); } // 3. 记录结果：当窗口长度达到 k 时（即 i >= k - 1） if (i >= k - 1) { result.push_back(nums[dq.front()]); // 队首就是当前窗口最大值 } } return result; } };

逐行拆解

以nums = [1, 3, -1, -3, 5, 3, 6, 7],k = 3为例：

• i = 0 (val=1):队列空，push_back(0)。dq = [0]。未满 k，不记录。

• i = 1 (val=3):nums[0]=1 <= 3，pop_back()弹出 0。push_back(1)。dq = [1]。未满 k。

• i = 2 (val=-1):nums[1]=3 > -1，保留。push_back(2)。dq = [1, 2]。

  • 检查过期：front=1，i-k = 2-3 = -1。1 > -1，未过期。

  • i >= k-1(2>=2)，记录nums[front] = nums[1] = 3。结果: [3]

• i = 3 (val=-3):nums[2]=-1 > -3，保留。push_back(3)。dq = [1, 2, 3]。

  • 检查过期：front=1，i-k = 0。1 > 0，未过期。

  • 记录nums[1] = 3。结果: [3, 3]

• i = 4 (val=5):nums[3]=-3 <= 5，弹出 3；nums[2]=-1 <= 5，弹出 2；nums[1]=3 <= 5，弹出 1。push_back(4)。dq = [4]。

  • 检查过期：front=4，i-k = 1。4 > 1，未过期。

  • 记录nums[4] = 5。结果: [3, 3, 5]

• ...以此类推，最终得到[3, 3, 5, 5, 6, 7]。