P3397扫描问题：使用单调队列优化代码解决超时问题

### 🍎 问题分析 原代码使用暴力法，每次移动窗口都遍历窗口内的所有元素来寻找最大值，时间复杂度达到了 $O(nk)$，当数据规模较大时（本题 $1\leq k\leq n\leq 2\times10^6$ ），这样的复杂度很容易导致超时（TLE）。为了优化时间复杂度，我们可以使用单调队列来解决这个问题，它可以将时间复杂度优化到 $O(n)$。 ### 💡 单调队列思路 单调队列是一种特殊的队列，它保证队列中的元素是单调递增或单调递减的。在本题中，我们使用单调递减队列，队列头部始终存储当前窗口内的最大值。 ### 📦 优化后的代码 ```cpp #include <iostream> #include <vector> #include <deque> using namespace std; // 函数用于找出每个窗口内的最大值 void maxSlidingWindow(const vector<int>& nums, int k) { int n = nums.size(); deque<int> dq; // 定义单调递减队列 // 先处理前 k 个元素，初始化队列 for (int i = 0; i < k; ++i) { // 当队列不为空且当前元素大于队列尾部元素时，弹出队列尾部元素 while (!dq.empty() && nums[i] >= nums[dq.back()]) { dq.pop_back(); } dq.push_back(i); // 将当前元素下标加入队列 } // 输出第一个窗口的最大值 cout << nums[dq.front()] << endl; // 处理剩余的元素 for (int i = k; i < n; ++i) { // 如果队列头部元素已经不在当前窗口内，弹出队列头部元素 if (!dq.empty() && dq.front() == i - k) { dq.pop_front(); } // 当队列不为空且当前元素大于队列尾部元素时，弹出队列尾部元素 while (!dq.empty() && nums[i] >= nums[dq.back()]) { dq.pop_back(); } dq.push_back(i); // 将当前元素下标加入队列 // 输出当前窗口的最大值 cout << nums[dq.front()] << endl; } } int main() { int n, k; // 读取数组长度 n 和窗口长度 k cin >> n >> k; vector<int> nums(n); // 读取数组中的元素 for (int i = 0; i < n; ++i) { cin >> nums[i]; } maxSlidingWindow(nums, k); return 0; } ``` ### 📋 代码解释 1. **初始化单调队列**：在 `maxSlidingWindow` 函数中，定义一个双端队列 `dq` 用于存储元素下标。首先处理前 `k` 个元素，当队列不为空且当前元素大于队列尾部元素时，弹出队列尾部元素，保证队列的单调性，最后将当前元素下标加入队列。 2. **输出第一个窗口的最大值**：队列头部元素的下标对应的元素就是当前窗口的最大值，输出该值。 3. **移动窗口并更新队列**：对于 `k` 到 `n - 1` 的元素，先检查队列头部元素是否已经不在当前窗口内，如果是则弹出队列头部元素。然后进行与初始化时相同的操作，保持队列的单调性。最后输出当前窗口的最大值。 ### ⚙️ 复杂度分析 - **时间复杂度**：$O(n)$，每个元素最多进队和出队一次。 - **空间复杂度**：$O(k)$，队列中最多存储 `k` 个元素。 ### 💡 开发建议 - **错误处理**：可以添加对输入的合法性检查，例如 `n` 和 `k` 是否满足题目要求的范围。 - **代码复用**：将单调队列的逻辑封装得更通用，方便在其他类似问题中复用。 - **边界情况考虑**：尤其是在处理队列的进出操作时，要仔细考虑边界情况，避免出现越界等错误。 ######[AI写代码神器 | 963点数解答 | 2026-08-15 16:12:03]