6.3 数据结构

这里介绍借助于特定数据结构的算法，它们代码量不会很大，但比较考验思维。

6.3.1 单调栈 *

单调栈是一种特殊的栈结构，它存储的元素从栈底到栈顶具有单调性。单调栈最朴素的用法是快速取得上一个比它小的元素。

作为一个例子，给定一个长度为 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 。这里用到一个单调递增栈。

#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int n;
int main() {
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        while (!s.empty() && s.top() >= x) {
            s.pop();
        }
        if (s.empty()) {
            cout << -1 << ' ';
        } else {
            cout << s.top() << ' ';
        }
        s.push(x);
    }
    return 0;
}

时间复杂度：#card=math&code=O%28n%29&id=pmfHh)

当然，它的用途绝不局限于这么简单。

例题：[USACO 2006 Nov S]Bad Hair Day

题目描述

Farmer John 的 N 头奶牛（ 头）的一些毛发不好！由于每头奶牛都对自己凌乱的发型有自我意识，因此 FJ 想计算能看到其他奶牛头顶的其他奶牛的数量。
每头奶牛 都有一个指定的高度 （），并且站在一排面向东方的奶牛中（在我们的图表中向右）。因此，奶牛 可以看到她面前奶牛的头顶（即奶牛 、 等），只要这些奶牛严格地比奶牛 矮。

考虑这个例子： =
= =
= =
= - =
= = =
= - = = =
= = = = = = 1 2 3 4 5 6

奶牛#1 可以看到奶牛的发型 #2, 3, 4
奶牛#2 看不到奶牛的发型
奶牛#3 可以看到奶牛的发型#4
奶牛#4 看不到奶牛的发型
奶牛#5 可以看到牛的发型 6
奶牛#6 根本看不到牛！
令 表示从奶牛 可以看到其发型的奶牛数量；请计算 到 的总和。对于此示例，所需答案为 3 + 0 + 1 + 0 + 1 + 0 = 5。

输入描述:

第 1 行：奶牛的数量，N。 第 2..N+1 行：第 i+1 行包含一个整数，即奶牛 i 的高度。

输出描述:

第 1 行：一个整数，它是 c1 到 cN 的总和。

示例1

输入

6 10 3 7 4 12 2

输出

5

考虑暴力解法：枚举奶牛，对于每一头奶牛，向右枚举矮于它的奶牛，直到遇见高于它的奶牛，统计数目。总体时间复杂度 #card=math&code=O%28n%5E2%29&id=rrDZR) ，一定会超时。

仔细思考解法的以下情况：

1. 对于一头奶牛，它可以看见右侧所有连续的更矮的奶牛，直到出现比它更高的奶牛。
2. 对于一头奶牛，它会阻挡左侧更矮的奶牛的视线，使它们再也看不见任何奶牛。

你是否读出了对使用单调栈的暗示？

考虑一个存储奶牛高度的单调递减栈。

进一步尝试，可以发现，对于上 1. 的情况，每在右侧新增一头更矮的奶牛，左侧连续的高于它的奶牛都会看见一头新的奶牛，而这个新增的数量就是单调栈内元素的数量；对于上 2. 的情况，每在右侧新增一头更高的奶牛，它会阻挡它左侧更矮的奶牛，表现为弹出小于等于它高度的元素，因为它们再也看不见奶牛，不会继续贡献答案。

最后，大数据记得开 long long 类型。

三年 OI 一场空，不开 LL 见祖宗。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<int> s;
int n;
int main() {
    cin >> n;
    ll ans = 0;
    while (n--) {
        int c;
        cin >> c;
        while (!s.empty() && s.top() <= c) {
            s.pop();
        }
        ans += s.size();
        s.push(c);
    }
    cout << ans << endl;
    return 0;
}

6.3.2 单调队列 *

例题：洛谷 P2032 扫描

这就是经典的「滑动窗口最大值」问题。

题目描述

有一个 的矩阵，有 个整数。

现在给你一个可以盖住连续 个数的木板。

一开始木板盖住了矩阵的第 个数，每次将木板向右移动一个单位，直到右端与第 个数重合。

每次移动前输出被覆盖住的数字中最大的数是多少。

输入格式

第一行两个整数 ，表示共有 个数，木板可以盖住 个数。

第二行 个整数，表示矩阵中的元素。

输出格式

共 行，每行一个整数。

第 行表示第 个数中最大值是多少。

输入输出样例

输入 #1 5 3 1 5 3 4 2

输出 #1 5 5 4

说明/提示

对于 。

对于 的数据，。

对于 的数据，，矩阵中的元素大小不超过 并且均为正整数。

维护一个队首到队尾的单调递减队列，最大元素会保持在队首。这个队列两端都需要弹出操作，需要使用 STL 的 deque<> 双端队列结构。另外，队列需要存储的是数组的下标，以识别队首元素是否需要被弹出。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 4;
int a[N];
deque<int> q;       // index of a[]
int n, k;
int main() {
    cin >> n >> k;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
    }
    for (int i=0; i<n; ++i) {
        int x = a[i];
        // 队首滑出窗口，则弹出
        if (q.front() + k - 1 < i) {
            q.pop_front();
        }
        // 队列保持单调递减
        while (!q.empty() && a[q.back()] <= x) {
            q.pop_back();
        }
        q.push_back(i);
        // 滑动窗口完全入场后，开始输出
        if (i >= k - 1) {
            cout << a[q.front()] << endl;
        }
    }
    return 0;
}

时间复杂度：#card=math&code=O%28n%29&id=N5jgP)

6.3.3 堆

现在你需要操作一个有序集合，频繁插入元素、删去最大/最小元素，并保持这个集合的有序性。堆结构能很好地支持这些功能，它本质上是一种树形结构，它每个节点的值都大于等于/小于等于其父亲节点的值，每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。它的插入、删除操作平均时间复杂度为 #card=math&code=O%28%5Clog%20n%29&id=SOIi8)，其维护 个元素的时间复杂度通常为 #card=math&code=O%28n%5Clog%20n%29&id=wyoVF)。

STL 提供了 priority_queue<>，是我们经常使用的堆结构。

// 大根堆，大的元素先弹出
priority_queue<int> q1;
// 小根堆，小的元素先弹出
priority_queue<int, vector<int>, greater<int> > q2;

例题：同「贪心 - 例题 2：[NOIP2004]合并果子」

已经做过了？再做一次试试吧。

练习：牛客 50439. tokitsukaze and Soldier *（难度较高）

参考：【每日一题】3月25日题目精讲 贪心、优先队列、堆

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
typedef long long ll;
struct Soldier {
    int v;      // 战力
    int s;      // 限制
    // 重载小于号，使默认从大到小排序
    bool operator< (const Soldier& rhs) const {
        return s > rhs.s;
    }
} a[N];
priority_queue<int, vector<int>, greater<int>> q;
int n;
int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a[i].v >> a[i].s;
    }
    sort(a, a + n);    // 按人数限制从大到小排序
    ll sum = 0, ans = 0;
    for (int i=0; i<n; ++i) {
        sum += a[i].v;
        q.push(a[i].v);
        // 人数超限，弹出
        while (q.size() > a[i].s) {
            sum -= q.top();
            q.pop();
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}