本文共 1320 字，大约阅读时间需要 4 分钟。
关于单调队列的讲解可看：
https://blog.csdn.net/roufoo/article/details/78443281
https://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html （单调队列的应用）
单调递增队列可以求滑动窗口的最小值（队首），单调递减队列可以求滑动窗口的最大值（队首）。 PS：本人的代码中是用STL中的deque双向队列实现的。 #include #include #include using namespace std;const int maxn = 1e6 + 6;int a[maxn];deque increaseQueue, decreaseQueue;int main(){ std::ios::sync_with_stdio(false); int n, k; cin>>n>>k; for(int i = 1; i <= n; ++i) cin>>a[i]; if(n <= k){ int maxID, minID = 1; for(int i = 1; i <= n; ++i){ if(a[maxID] < a[i]) maxID = i; if(a[minID] > a[i]) minID = i; } cout< < a[i]) increaseQueue.pop_back(); increaseQueue.push_back(i); while(!decreaseQueue.empty() && a[decreaseQueue.back()] < a[i]) decreaseQueue.pop_back(); decreaseQueue.push_back(i); } for(int i = k; i <= n; ++i){ if(!increaseQueue.empty() && i - increaseQueue.front() >= k) increaseQueue.pop_front(); while(!increaseQueue.empty() && a[increaseQueue.back()] > a[i]) increaseQueue.pop_back(); increaseQueue.push_back(i); if(i != n) cout< <<" "; else cout< < = k) decreaseQueue.pop_front(); while(!decreaseQueue.empty() && a[decreaseQueue.back()] < a[i]) decreaseQueue.pop_back(); decreaseQueue.push_back(i); if(i != n) cout< <<" "; else cout< <