滑动窗口最大值和最小值

题目：

思路：

窗口进行滑动时，需要快速获取min和max，因此需要一个结构来保存最值，而不是临时计算。动态的最值更新容易联想到单调栈，但是这里需要频繁增删元素，因此用双端队列，front删除移除窗口的元素，back增添移入窗口的元素。
创建两个双端队列，一个记录窗口最小值，一个记录窗口最大值。
最小值双端队列中递增排序，首元素就是当前窗口中的最小值。每次窗口移动1位，首先判断位于队首的元素是否被移除窗口，如果是，出队，否则将新元素与队尾元素比较，如果大于队尾元素直接入队，否则将队尾元素出队，直至新元素入队，作为备选的最小值。
最大值双端队列中递减排序，其他操作与最小值双端队列类似。

代码：

#include<iostream>
#include<vector>
#include<deque>
using namespace std;void slidingWindow(const vector<int>& arr, int k, vector<int>& mins, vector<int>& maxs)
{deque<int> min_q, max_q;for (int i = 0; i < arr.size(); i++){//移除不在窗口中的元素while (!min_q.empty() && min_q.front() <= i - k)min_q.pop_front();while (!max_q.empty() && max_q.front() <= i - k)max_q.pop_front();//维护最小值队列while (!min_q.empty() && arr[i] <= arr[min_q.back()])min_q.pop_back();min_q.push_back(i);//维护最大值队列while (!max_q.empty() && arr[i] >= arr[max_q.back()])max_q.pop_back();max_q.push_back(i);//当窗口形成时记录结果if (i >= k - 1){mins.push_back(arr[min_q.front()]);maxs.push_back(arr[max_q.front()]);}}
}int main()
{int n, k;cin >> n >> k;vector<int> arr(n);for (int i = 0; i < n; i++)//获取数组cin >> arr[i];vector<int> mins, maxs;slidingWindow(arr, k, mins, maxs);for (int num : mins)cout << num << " ";cout << endl;for (int num : maxs)cout << num << " ";cout << endl;return 0;
}

 运行结果：