题目链接

算法竞赛进阶指南-48.双端队列

达达现在碰到了一个棘手的问题，有 $N$ 个整数需要排序。

达达手头能用的工具就是若干个双端队列。

她从 $1$ 到 $N$ 需要依次处理这 $N$ 个数，对于每个数，达达能做以下两件事：

1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；

2．将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。

请你求出最少需要多少个双端序列。

输入格式

第一行输入整数 $N$，代表整数的个数。

接下来 $N$ 行，每行包括一个整数 $D_i$，代表所需处理的整数。

输出格式

输出一个整数，代表最少需要的双端队列数。

数据范围

$1 \le N \le 200000$

输入样例：

6
3
6
0
9
6
3

输出样例：

2

Method : 贪心

可以发现该题有两个性质：

1. 在最优解中，每一个双端队列，必定是有序数组中的一个连续子序列
2. 每个双端队列的下标是先减少后递增的 “单谷” 形式（因为之后插入的数要么接在队首，要么队尾）

因此，可以对原数组先排序，然后根据下标找 “单谷” 计算最优解:

具体做法可以用一个pair<int, int>存储{数值，下标}，对其先排序，使得相同的数放在一起看作一个区间：

如题给数据：$[[0], [3, 3], [6, 6], [9]]$， 对应下标$[[3], [1, 6], [2, 5], [4]]$

用一个变量$dir$记录当前是上升趋势还是下降趋势，并用另一个变量$last$记录上一个区间的最后一个下标大小

初始时默认先开辟一个双端队列, 并从无穷大开始下降: res = 1, dir = -1, last = INT_MAX

1. 如果当前处于下降趋势

   • 下标最大值小于最后一个元素的下标，按下标降序接在后面，整体下标呈\形
   • 下标最大值大于最后一个元素的下标，按下标升序接在后面，整体下标呈 \/ 形，变为上升趋势

2. 如果当前处于上升趋势

   • 下标最小值大于最后一个元素的下标，按下标升序接在后面，整体呈/形
   • 下标最小值小于最后一个元素的下标，按下标降序接在后面，整体呈 /\形，变为下降趋势

   并且注意：当由上升趋势变为下降趋势后，相当于开辟了一个新的单谷，因此res ++

#include <iostream>
#include <algorithm>
#include <limits.h>

using namespace std;

typedef pair<int, int> PII; // {数值, 下标}

const int N = 2e5 + 7;

int n;
PII a[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    
    sort(a + 1, a + 1 + n);
    
    int res = 1;
    int last = INT_MAX, dir = -1; // -1 下降; 1 上升
    for (int i = 1; i <= n; ) {
        int j = i + 1;
        while (j <= n && a[j].first == a[i].first) j ++;
        
        int max_idx = a[j - 1].second, min_idx = a[i].second;
        if (dir == -1) {
            if (last > max_idx) last = min_idx; // 延续
            else {
                dir = 1;
                last = max_idx;
            }
        }
        else {
            if (last < min_idx) last = max_idx; // 延续
            else {
                dir = -1;
                last = min_idx;
                res ++;
            }
        }
        i = j;
    }
    
    cout << res << endl;
    return 0;
}

复杂度分析

• 时间复杂度：${O(n\log n + n)}$， 其中$n\log n$为sort排序的时间复杂度。

• 空间复杂度：${O(N)}$。