Java教程

算法学习(8):单调队列

本文主要是介绍算法学习(8):单调队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

单调队列

单调队列是一种主要用于解决滑动窗口类问题的数据结构,即,在长度为n的序列中,求每个长度为m的区间的区间最值。

//得到的是一个单调递减的队列
deque<int> Q; // 存储的是编号
for (int i = 0; i < n; ++i)
{
    if (!Q.empty() && i - Q.front() >= m) //编号在当前滑动窗口外
        Q.pop_front();
    while (!Q.empty() && V[Q.back()] < V[i]) //新加进的数比之前的都要大
        Q.pop_back();
    Q.push_back(i); // 入队
    if (i >= m - 1)
        cout << V[Q.front()] << " ";
}
这篇关于算法学习(8):单调队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!