【题解】合并排序

题意

给你一个长度为且各个元素不同的数组，问将数组，划分为个区间，对每个区间内部进行从大到小排序，且让整体是从大到小有序的。问最大的是多少。

题解

由于序列中的每个数都不同，可以将元素映射到。排序完之后就是的形式。我们对于每个数字可以将其现在的位置与排序后所在的位置看成一段区间，也就是说若要到他最终的位置，必须跨越这段区间，所以每个数字可以有一段区间。若两段区间之间有交叉也就是排序时两个区间必须合并。所以我们可以将区间按左端点进行排序之后从头到尾合并一下，最后剩下几个不重叠的区间也就是要找的最大的。

复杂度

排序复杂度
合并时间复杂度

代码

c++

const int N=1e5+5;
struct node
{
    int l,r;
}d[N];
map<int,int>vis;
bool cmp(node a,node b)
{
    return a.l<b.l;
}
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最大的k
     * @param n int整型 数组长度
     * @param a int整型vector 数组a
     * @return int整型
     */
    int MaxK(int n, vector<int>& a) {
        // write code here
        vector<int>b=a;
        sort(b.begin(),b.end(),greater<int>());
        for(int i=0;i<n;i++)
        vis[b[i]]=i;
        for(int i=0;i<n;i++)
        {
            d[i].l=min(i,vis[a[i]]);
            d[i].r=max(i,vis[a[i]]);
        }
        sort(d,d+n,cmp);
        int ans=1;
        node merged=d[0];
        for(int i=1;i<n;i++)
        {
            if(merged.r<d[i].l)
            {
                merged=d[i];
                ans++;
            }
            else
            {
                merged.r=max(d[i].r,merged.r);
            }
        }
        return ans;
    }
};

python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 返回最大的k
# @param n int整型 数组长度
# @param a int整型一维数组 数组a
# @return int整型
#
class Solution:
    def MaxK(self , n , a ):
        # write code here
        b = [0 for i in range(n)]
        for i in range(n):
            b[i]=a[i]
        b.sort(reverse=True)
        vis = {}
        for i in range(n):
            vis[b[i]]=i
        d=[]
        for i in range(n):
            l=min(i,vis[a[i]])
            r=max(i,vis[a[i]])
            d.append([l,r])
        d.sort()
        ans=1
        merged=d[0]
        for i in range(1,n):
            if merged[1]<d[i][0]:
                merged=d[i]
                ans+=1
            else:
                merged[1]=max(d[i][1],merged[1])
        return ans