题目描述

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

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

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

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

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

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

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

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

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

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

数据范围
1≤N≤200000

样例

输入样例：
6
3
6
0
9
6
3
输出样例：
2

直接模拟求解很难，局部决策可能会导致后面有一个数大小位于已经插入的两个数中间，
因为只能使用双端队列，所以错误
反向思考问题,把一个A[ 1 , n ]的已经排好顺序的序列,分成尽量少的段,
每一段都是一个双端队列.

单谷性质（先单减，后递增）
开一个数组也就是B数组,记录原数组A的每一个数的下标,然后我们发现如果B的一段满足单单谷性质,
那么这一段就可以形成合法的双端序列.
因为单谷性质,前半段可以视为从队头加入,后半段视为从队尾加入.
数值相同的点的下标可以交换用来满足单谷序列
所有值相同的都是一个vector，对于每一个值的下标都从小到大排序
贪心过程：
求单调递减时候，如果上一个点的下标比当前值下标最大的还要大，
那么显然将下标最小的点放到最后可以将所有当前值都存入，
否则就证明到达谷底，结束的即为当前最大值，因为接下来就要检查递增，
而递增是优先放下标最大的所以如果转到求递增的时候，下标是连续的相同值的下标，显然最优
求递增的时候如果值相同，上一个点的下标比当前的值下标最小的还要小就一定可以一直放，直到最大
贪心求得最少的谷底数，即为最少的单谷段，即答案

时间复杂度

O（nlogn）

C++ 代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
pii a[N];
vector<int>p[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].fi;
        a[i].se=i;
    }
    sort(a,a+n);
    int tot=0;
    for(int i=0;i<n;i++){
        p[++tot].pb(a[i].se);//tot从1开始会方便下面的push_back操作
        while(a[i+1].fi == a[i].fi)
            p[tot].pb(a[++i].se);
    }
    for(int i=1;i<=tot;i++)
        sort(p[i].begin(),p[i].end());

    bool flag=0;//记录是否到达转折点
    int pos=INT_MAX,ans = 1;
    for(int i=1;i<=tot;i++){
        int ed=p[i].size()-1;
        if(flag){//求递增
            if(pos < p[i][0])
                pos = p[i][ed];//无法递增移动端点，区间个数+1
            else{
                ++ans;
                pos = p[i][0];
                flag=0;
            }
        }
        else {//求递减
            if(pos > p[i][ed])
                pos = p[i][0];
            else{
                flag = 1;
                pos = p[i][ed];
            }
        }
    }
    cout<<ans<<endl;
}