深入浅出单调栈与单调队列

由于每个元素一定会被压入一次且至多弹出一次，因此操作次数至多是

2

n

2n

2n，故总时间复杂度为

O

(

n

)

O(n)

O(n)。

#include 

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack stk;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i > a[i];

    for (int i = 0; i < n; i++) {
        while (!stk.empty() && stk.top() >= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(a[i]);
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

📝 代码完全可以简化，之所以这么写是为了方便统一格式。

情形二：寻找一个数左边第一个小于它的数的下标

和情形一类似，只不过这里我们寻找的是下标，如果不存在则输出

−

1

-1

−1。

只需对栈做一点小小的修改就能应对情形二。注意到之前我们寻找的是元素所以让栈去保存元素，现在我们寻找下标，所以让栈去保存元素的下标就可以了。

#include 

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack stk;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i > a[i];

    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[stk.top()] >= a[i]) stk.pop();  // 仅有两处修改
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(i);  // 仅有两处修改
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

情形三：寻找一个数右边第一个大于它的数

之前我们是在一个数的左边去寻找，所以让栈去保存这个数左边的所有数，类似地，现在需要让栈去保存这个数右边的所有数。

考虑将数组翻转（实际上不可能翻转，而是倒序遍历），因此情形三变成了「寻找一个数左边第一个大于它的数」，于是归结为情形一。

#include 

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack stk;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i > a[i];

    for (int i = n - 1; ~i; i--) {
        while (!stk.empty() && stk.top() <= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(a[i]);
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

情形四：寻找一个数右边第一个大于它的数的下标

结合情形二和情形三即可得出。

#include 

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack stk;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i > a[i];

    for (int i = n - 1; ~i; i--) {
        while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(i);
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

不难发现，这四种情形只在第

16

,

17

,

20

16,17,20

16,17,20 行不同，其余部分的代码均相同，据此可以总结出以下三点区别：

• 遍历顺序（以怎样的顺序遍历数组

  a

  a

  a）；

• 比较方式（如何比较当前元素和栈顶元素）；
• 栈中存储的是什么（是元素本身还是元素的下标还是其他）。

二、单调栈的应用

2.1 单调栈模板题I

原题链接：AcWing 830. 单调栈

此题对应情形一，不再赘述，直接给出AC代码。

#include 

using namespace std;

stack stk;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        while (!stk.empty() && stk.top() >= x) stk.pop();
        if (!stk.empty()) cout << stk.top() << ' ';
        else cout << -1 << ' ';
        stk.push(x);
    }

    return 0;
}

2.2 单调栈模板题II

原题链接：洛谷 P5788 【模板】单调栈

此题对应情形四，不再赘述，直接给出AC代码。

#include 

using namespace std;

const int N = 3e6 + 10;

int a[N], ans[N];
stack stk;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i > a[i];

    for (int i = n; i; i--) {
        while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        stk.push(i);
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';

    return 0;
}

2.3 Bad Hair Day

原题链接：POJ 3250 Bad Hair Day

本题类似于情形四，但还是有些区别。

首先应当注意到以下几点：

• 每头牛只向右看；
• 每头牛只能看见比自己低的牛的头顶；
• 若两头牛一样高，则它们互相看不到对方的头顶。

这相当于对数组中的某个数，我们要在它的右边寻找第一个大于等于它的数的下标，知道下标后，我们就可以算出这头牛能够看到多少头牛的头顶了。当然，如果找不到这样的数，说明这头牛的右边全是比它低的牛，此时用牛的数量减去该牛的下标（从

1

1

1 开始）就是该牛能够看到的头顶的数量。

还需注意一个问题，假设给定的序列是单调递减的，那么所求答案为

N

(

N

−

1

)

/

2

≈

3

×

1

0

9

N(N-1)/2\approx 3\times 10^9

N(N−1)/2≈3×109，会爆 int。

#include 

using namespace std;

typedef long long LL;

LL h[80010], ans;
stack stk;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);

    for (int i = n; i; i--) {
        while (!stk.empty() && h[stk.top()] < h[i]) stk.pop();
        if (!stk.empty()) ans += stk.top() - i - 1;
        else ans += n - i;
        stk.push(i);
    }

    printf("%lld", ans);

    return 0;
}

三、单调队列

单调队列的定义类似于单调栈：

• 单调递增队列： 从队尾到队头单调递增；
• 单调递减队列： 从队尾到队头单调递减。

例如对于单调递增队列，向其中插入元素的时候，为了维护队列的单调性，需要在保证将该元素插入到队尾后整个队列满足单调性的前提下弹出最少的元素（从队尾弹出）：

deque q;  // 因为涉及到从队尾弹出，所以只能用双端队列来实现单调队列

void insert(int x) {
    while (!q.empty() && q.back() < x)
        q.pop_back();
    q.push_back(x);
}

⚠️ 严格意义上讲单调队列并不是队列，因为它不满足FIFO。

四、单调队列的应用

4.1 滑动窗口

原题链接：AcWing 154. 滑动窗口

单调队列常用于求滑动窗口中的最大（小）值。我们先来看一下这道题的暴力解法是什么样的：

#include 

using namespace std;

typedef long long LL;

const LL INF = 3e9;

LL a[1000010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 0; i > a[i];

    for (int i = 0; i <= n - k; i++) {
        LL mini = INF;
        for (int j = i; j < i + k; j++) mini = min(mini, a[j]);
        cout << mini << ' ';
    }

    cout << "\n";

    for (int i = 0; i <= n - k; i++) {
        LL maxi = -INF;
        for (int j = i; j < i + k; j++) maxi = max(maxi, a[j]);
        cout << maxi << ' ';
    }

    return 0;
}

显然时间复杂度为

O

(

n

k

)

O(nk)

O(nk)，基本会TLE。使用单调队列，我们可以将时间复杂度降低至

O

(

n

)

O(n)

O(n)。

以求最小值为例，我们使用单调递减队列来保存滑动窗口中的元素，下标越大的元素越接近队尾，下标越小的元素越接近队头，于是求滑动窗口中的最小值相当于访问队头元素。

不妨设下标从

1

1

1 开始，初始时

i

i

i 指向

1

1

1，并且

i

i

i 从

1

1

1 遍历至

n

n

n，每次遍历都将

a

[

i

]

a[i]

a[i] 插入到队列中。可以发现，只要有

i

<

k

i< k

i<k 就说明滑动窗口还未形成，此时无需输出最小值，当

i

≥

k

i\geq k

i≥k 时才需要输出最小值。

那何时弹出队头元素呢？不妨让单调队列保存的是元素的下标而非元素本身，设当前窗口为

a

[

i

−

k

.

.

i

−

1

]

a[i-k..i-1]

a[i−k..i−1]，向单调队列插入

i

i

i 后，新窗口变成

a

[

i

−

k

+

1..

i

]

a[i-k+1..i]

a[i−k+1..i]，如果队头元素小于等于

i

−

k

i-k

i−k，说明最小值不在新窗口中，此时应当弹出队头元素。

到目前为止，可以总结出两点：

• 只要

  i

  ≥

  k

  i\geq k

  i≥k 就应当输出队头元素；

• 当队头元素小于等于

  i

  −

  k

  i-k

  i−k 时，弹出队头元素。

#include using namespace std;const int N = 1e6 + 10;int a[N];deque q;int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n, k;    cin >> n >> k;    for (int i = 1; i > a[i];    for (int i = 1; i <= n; i++) {        while (!q.empty() && a[q.back()] > a[i]) q.pop_back();        q.push_back(i);        if (!q.empty() && q.front() = k) cout << a[q.front()] << ' ';    }    cout << "\n";    q.clear();    for (int i = 1; i <= n; i++) {        while (!q.empty() && a[q.back()] < a[i]) q.pop_back();        q.push_back(i);        if (!q.empty() && q.front() = k) cout << a[q.front()] << ' ';    }    return 0;}

此题还可以用优先队列来做，为避免不必要的判断，我们可以在一开始就向队列中插入前

k

k

k 个元素：

#include 

using namespace std;

typedef pair PII;
const int N = 1e6 + 10;

int a[N];
priority_queue p;  // 大根堆
priority_queue<PII, vector, greater> q;  // 小根堆

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 1; i > a[i];

    for (int i = 1; i <= k; i++) q.emplace(a[i], i);
    cout << q.top().first << ' ';

    for (int i = k + 1; i <= n; i++) {
        q.emplace(a[i], i);
        while (!q.empty() && q.top().second <= i - k) q.pop();  // 只能用while
        cout << q.top().first << ' ';
    }

    cout << "\n";

    for (int i = 1; i <= k; i++) p.emplace(a[i], i);
    cout << p.top().first << ' ';

    for (int i = k + 1; i <= n; i++) {
        p.emplace(a[i], i);
        while (!p.empty() && p.top().second <= i - k) p.pop();  // 只能用while
        cout << p.top().first << ' ';
    }

    return 0;
}

观察上面两段代码，可以发现思路是大致相同的，但区别在于（请看注释行），单调队列在弹出队头元素的时候既可以用 if 也可以用 while，而优先队列弹出队头元素的时候只能用 while，这是为什么呢？

考虑数组

[

4

,

6

,

2

,

3

,

5

,

1

,

8

,

7

,

9

]

[4,6,2,3,5,1,8,7,9]

[4,6,2,3,5,1,8,7,9]，窗口大小为

3

3

3，以求最小值为例，每次循环结束后单调队列和优先队列的状态列在下表中：

⚠️ 列表的左端是队头，右端是队尾。

⚠️ 对于优先队列，只需看列表的第一个元素，其后元素的次序无关紧要。

因为优先队列在插入元素的过程中不会弹出元素，所以只要队头位于窗口内，那么优先队列的大小只增不减，这就导致优先队列中存在许多冗余元素（不属于窗口内的元素）。而单调队列为了保持单调性，插入元素的时候会从队尾弹出一些元素，这就保证了单调队列中的元素始终是滑动窗口中的元素的子集，因此单调队列的 while 循环至多执行一次，自然可以改成 if。