C++实现滑动窗口最大值输出的解决方案及开发建议

### 🌟解题思路 本题要求在一个长度为 `n` 的数组中，使用长度为 `k` 的滑动窗口，每次输出窗口内的最大值。可以通过遍历数组，每次取窗口内的元素并找出最大值进行输出。 ### 💻代码实现 ```cpp #include <iostream> #include <vector> using namespace std; // 函数用于找出给定窗口范围内数组中的最大值 int findMaxInWindow(const vector<int>& arr, int start, int end) { int maxVal = arr[start]; for (int i = start + 1; i < end; ++i) { if (arr[i] > maxVal) { maxVal = arr[i]; } } return maxVal; } int main() { int n, k; // 读取数组长度 n 和窗口长度 k cin >> n >> k; vector<int> arr(n); // 读取数组中的元素 for (int i = 0; i < n; ++i) { cin >> arr[i]; } // 遍历数组，移动窗口 for (int i = 0; i <= n - k; ++i) { // 输出当前窗口内的最大值 cout << findMaxInWindow(arr, i, i + k) << endl; } return 0; } ``` ### 📝代码解释 1. **`findMaxInWindow` 函数**：该函数接受一个整数向量 `arr` 以及窗口的起始和结束位置作为参数，通过遍历窗口内的元素找出最大值并返回。 2. **主函数 `main`**： - 首先读取数组的长度 `n` 和窗口的长度 `k`。 - 接着读取数组中的所有元素并存储在向量 `arr` 中。 - 然后通过一个循环移动窗口，每次调用 `findMaxInWindow` 函数找出当前窗口内的最大值并输出。 ### ⚙️复杂度分析 - **时间复杂度**：$O(nk)$，其中 $n$ 是数组的长度，$k$ 是窗口的长度。因为对于每个窗口，都需要遍历窗口内的 $k$ 个元素来找出最大值，总共需要遍历 $n - k + 1$ 个窗口。 - **空间复杂度**：$O(n)$，主要用于存储输入的数组。 ### 💡开发建议 - **使用单调队列优化**：当前代码的时间复杂度较高，可以使用单调队列（如双端队列）来优化，将时间复杂度降低到 $O(n)$。单调队列可以在 $O(1)$ 时间内找出窗口内的最大值，从而提高程序的性能。 - **边界检查**：在实际开发中，需要对输入进行边界检查，确保输入的 `n` 和 `k` 满足 $1\leq k\leq n\leq 2\times10^6$ 的条件，避免出现越界等错误。 - **代码可读性**：可以添加更多的注释，特别是在关键逻辑部分，以提高代码的可读性，方便后续维护。 ######[AI写代码神器 | 718点数解答 | 2026-08-15 16:10:19]