单调队列

                     

贡献者: 有机物

预备知识 队列

   单调队列和单调栈类似,内部的元素都是单调递增或者递减的,单调队列的思想也是及时排除一定不是最优的选择。单调队列的时间复杂度也是 $O(n)$。

   单调队列通常处理滑动窗口类的问题,例题。 题意大致为:有一个大小为 $k$ 的滑动窗口,每次要输出窗口中的最大值和最小值。

   举例:

   该数组为 [1 3 -1 -3 5 3 6 7],$k$ 为 $3$。

表1:示例
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

   同样,我们来思考一下朴素算法怎么做,我们用一个队列(这里的队列指双端队列,两端都可以弹出元素)来维护窗口,每次往后移动一位就是往队尾插入一个数,队头删除一个数。要移动 $k$ 次窗口,每次求最小值和最大值就线性枚举一下整个队列,时间复杂度 $O(n\times k)$。

   如何去优化?思想和单调栈类似,如果 $a_i \geqslant a_j$,那显然 $a_i$ 永远不会作为答案输出。因为 $a_j$ 比 $a_i$ 小,因为求的是最小值,所以输出 $a_j$ 肯定比输出 $a_i$ 要好,所以遇到这种情况就直接把 $a_i$ 删了就行了。所以删除完之后,队列中的元素也就单调上升了。那具有单调性有什么用呢?没有单调性之前要求出最小值我们需要 $O(n)$ 的时间复杂度扫描一遍,具有单调性之后,队头肯定是最小的元素,所以直接 $O(1)$ 输出队头元素就好了。所以单调队列的时间复杂度就是 $O(n)$。

   具体做法:每次加入一个元素之前判断元素队尾元素是不是比要插入的元素大或相等,如果满足的话删除队尾元素,所以求最小值直接输出队头元素。

cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];

int hh = 0, tt = -1;  // hh 队头,tt 队尾
for (int i = 0; i < n; i ++ )
{
    if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;  // 如果队列大小大于窗口的大小,则队头出队
    while (hh <= tt && a[i] <= a[q[tt]]) tt -- ;
    q[ ++ tt] = i;
    if (i + 1 >= k) cout << a[q[hh]] << ' ';    // i + 1 就是满足窗口大小的队列,每次输出队头
}
cout << endl;

hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
    while (hh <= tt && a[i] >= a[q[tt]]) tt -- ;  // 求最大值过程对称做一下
    q[ ++ tt] = i;
    if (i + 1 >= k) cout << a[q[hh]] << ' ';
}


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利