[單調隊列+模闆] 單調隊列模闆

文章目錄

• • 0. 前言
  • 1. 單調隊列

0. 前言

Biu

單調隊列主要用于求取一個區間的最大最小值。

最為經典的應用是 滑動視窗 問題，我遇到的題目比較少，在此僅總結代碼模闆，可能不适用普遍學習者。

單調隊列也分為兩種，單調遞增、遞減隊列，适用于不同場景，以後會根據題目來使用。

1. 單調隊列

這裡是拿數組模拟隊列，一定需要注意的是

q[tt++] = i

入隊的過程需要放到判斷之前，即如果因為目前入隊元素很小，将隊列給清空了，那麼目前應該列印這個元素，是以應該放在判斷之前，這個踩坑了，一定注意。

判斷隊頭是否已經滑出視窗，這裡采用的是

if

，因為每次視窗隻會向後滑動一位，是以每次也隻可能一個元素滑出了視窗，但是大多數情況下應該采用

while

因為滑出視窗的元素，對于本題來講沒有絲毫意義，對于單調隊列維護的這個區間來講也沒有任何意義。 是以建議還是采用

while

比較好，減少這些分析的時間。

至于判斷隊頭元素是否在視窗内，直接采用下标相減的方式進行判斷即可。

對于滑動視窗中最大值的選取也是一樣的操作，僅需要改變

while

内的判斷條件即可。

模闆代碼：

#include <iostream>

using namespace std;

const int N = 1e6+5;

int n, k;
int a[N], q[N], hh, tt;

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    hh = 0, tt = -1;
    for (int i = 0; i < n; ++i) {       // 最小值
        // 判斷隊頭是否已經劃出視窗
        if (hh <= tt && i - k + 1 > q[hh]) hh ++;   // 用while比較保險，但是針對for來講隻會有一次隊頭不滿足的情況
        while (hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[++ tt] = i;   // 要在if前把i加進去，因為如果a[i]很小，把隊列全部清空，應該是傳回a[i]的
        if (i >= k - 1) cout << a[q[hh]] << ' ';
    }
    puts("");
    
    hh = 0, tt = -1;
    for (int i = 0; i < n; ++i) {       // 最大值   僅需要改變while的小于等于即可
        // 判斷隊頭是否已經劃出視窗
        while (hh <= tt && i - k + 1 > q[hh]) hh ++;    // if while 均可
        while (hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[++ tt] = i;
        if (i >= k - 1) cout << a[q[hh]] << ' ';
    }
    
    return 0;
}