双端队列 题解

题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1\le N\le 200000$

输入样例：

6
3
6
0
9
6
3

输出样例：

2

---

时间复杂度 $\mathcal{O}(nlogn)$

C++ 代码

/*
1.最后合并所有双端队列dq的序列，每个dq都占最后序列的连续一段。
2.对于任意dq中的每一个数，其对应的原来数组中的下标都是先下降后上升。 例如 32145，1是第一个插入的数，后序只能在在两侧插入
3.所以问题转化为，原序列排序后，最少能分为多少个（原下标先下降后上升）的部分或区间。
4.由于排序后，相同的数字之间可以交换，所以可以通过交换相同的数字来交换下标，有了操作空间。
5.将连续相同数字子序列看为一个个单独区间，贪心去做。
6.当上一个区间末尾是下降的时候，当前的区间希望能调整成下降序列（原下标下降），要求是当前的最大下标小于上一段的末尾。
7.反之，上一个区间末尾上升，则希望当前区间调整成上升序列，要求当前区间最小下标大于上一个区间末尾。
8.不满足就接不上。当上一个区间上升而当前区间接不上的时候，相当于一个谷结束了，则此时需要一个新的dq。
*/

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

typedef pair<int,int> PII;  // <值，下标>

const int N = 2e5 + 10;

int n;
PII a[N];

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i){
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a, a + n);
    
    int dir = -1, last = INT_MAX;  // dir=-1表示下降， last表示上一个区间末尾下标
    
    int ans = 1;  // 一开始有一个队列放(从last下降下来)
    
    for(int i = 0; i < n; ){
        int j = i;
        while(j < n && a[j].first == a[i].first) j ++;
        
        int minp = a[i].second, maxp = a[j - 1].second;  // 由于pair排序还会对second进行从小到大排序，所以最小的下标就是第一个i的second
        
        if(dir == -1){
            if(maxp < last) last = minp;
            else last = maxp, dir = 1;  // dir换方向
            // last不会等于maxp的，因为他们都是下标，下标没有重复
        }
        else{
            if(minp > last) last = maxp;
            else last = minp, dir = -1, ans ++;
        }
        i = j;
    }
    
    printf("%d\n", ans);
    
}