POJ 2823 是一个经典的滑动窗口问题，题目要求在一个数组中找到每个长度为 k 的子数组的最小值和最大值。
题目描述
给定一个长度为 n 的整数数组和整数 k，对于数组中的每个连续子数组长度为 k，输出每个子数组的最小值和最大值。
输入
- 第一行包含两个整数 n 和 k，分别表示数组的长度和子数组的长度。
- 第二行包含 n 个整数，表示数组中的元素。
输出
- 第一行包含 n-k+1 个整数，表示每个长度为 k 的子数组的最小值。
- 第二行包含 n-k+1 个整数，表示每个长度为 k 的子数组的最大值。
解决思路
滑动窗口问题通常可以使用双端队列（deque）来高效解决。双端队列可以在两端进行插入和删除操作，非常适合维护窗口内的最大值和最小值。
具体步骤
-
初始化：
- 创建两个双端队列
minDeque和maxDeque，分别用于存储窗口内的最小值和最大值的索引。 - 创建两个结果数组
minResult和maxResult，用于存储每个窗口的最小值和最大值。
- 创建两个双端队列
-
遍历数组：
- 对于数组中的每个元素，进行以下操作：
- 维护最小值队列：
- 移除队列中所有大于当前元素的值，因为这些值不可能成为后续窗口的最小值。
- 将当前元素的索引添加到队列尾部。
- 如果队列头部的索引已经不在当前窗口内，移除它。
- 维护最大值队列：
- 移除队列中所有小于当前元素的值，因为这些值不可能成为后续窗口的最大值。
- 将当前元素的索引添加到队列尾部。
- 如果队列头部的索引已经不在当前窗口内，移除它。
- 对于数组中的每个元素，进行以下操作：
-
记录结果：
- 当窗口形成后（即遍历到第 k 个元素后），开始记录每个窗口的最小值和最大值。
- 最小值即为
minDeque队头索引对应的元素，最大值即为maxDeque队头索引对应的元素。
代码实现
以下是使用 C++ 实现的代码示例：
#include
using namespace std;
void slidingWindowMinMax(const vector
for (int i = 0; i < n; ++i) {
// 维护最小值队列
while (!minDeque.empty() && nums[minDeque.back()] >= nums[i]) {
minDeque.pop_back();
}
minDeque.push_back(i);
if (minDeque.front() == i - k) {
minDeque.pop_front();
}
// 维护最大值队列
while (!maxDeque.empty() && nums[maxDeque.back()] <= nums[i]) {
maxDeque.pop_back();
}
maxDeque.push_back(i);
if (maxDeque.front() == i - k) {
maxDeque.pop_front();
}
// 记录结果
if (i >= k - 1) {
minResult.push_back(nums[minDeque.front()]);
maxResult.push_back(nums[maxDeque.front()]);
}
}}
int main() {
int n, k;
cin >> n >> k;
vector
vector minResult, maxResult;
slidingWindowMinMax(nums, k, minResult, maxResult);
for (int val : minResult) {
cout << val << " ";
}
cout << endl;
for (int val : maxResult) {
cout << val << " ";
}
cout << endl;
return 0; }
解释
- 双端队列：用于存储当前窗口内的最小值和最大值的索引，确保队列头始终是当前窗口的最小值或最大值的索引。
- 维护队列：在遍历数组时，通过比较当前元素与队列尾部的元素，移除不可能成为最小值或最大值的元素，确保队列的有效性。
- 记录结果：当窗口形成后，队列头部的索引对应的元素即为当前窗口的最小值或最大值。
这种方法的时间复杂度为 O(n)，因为每个元素最多被插入和删除一次。
希望这个详细的解答能帮助你理解和解决 POJ 2823 问题。如果有任何进一步的问题，欢迎继续提问！
发表回复