NC566 题解 | #连续段的中数#

题意分析

• 给我们一个序列，要我们找出一个长度大于等于k的序列，然后这个序列里面的中数要尽可能大。“中数”的定义就是这个序列里面大于等于这个数字的个数要大于等于这个序列的长度的一半。所以在保证这个序列是升序排列的情况下，下图所示的就是中数。

思路分析

解法一 暴力枚举+优先队列维护

• 这个思路就是，我们先枚举这个序列的长度，然后对于每个长度满足题目条件的子序列，我们枚举左端点，那么右端点自然就能够找到了，找到这个序列区间之后，我们再找出这个区间里面的中数，用一个变量记录下来维护最大值就行了。

• 怎么快速找到这个区间的中数呢？其实这里可以和区间第K大的数，这个经典的算法模板相结合。我们用对顶堆来进行维护区间的中数。我们不断地维护两个堆地大小，使他们的大小尽可能地相差不大。如果相差一旦超过2，我们就对他们进行调整，这种，遍历了区间所有的数字之后，我们就可以根据区间长度奇偶性找到中数了。

• 这里大致地介绍一下堆

• 代码如下
  • 首先，枚举了长度，时间复杂度为,然后枚举了左端点，区间复杂度变为.然后，我们对区间进行了遍历，同时利用对顶堆进行维护，这里的时间复杂度为.最后，时间复杂度为。
  • 我们需要利用数组存储序列的数字，空间复杂度为，我的这种方法目前是空间复杂度最好的

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a) {
        // write code here
        int ans=0;
        // 第一维，枚举长度
        for(int len=k;len<=n;len++){
            // 第二维，枚举当前长度的所有的连续序列的左端点
            for(int j=0;j+len-1<n;j++){
                // 对于每个连续的序列，我们进行判断
                // 这里就转化为求区间第k大数的模型了
                priority_queue<int> sml;// 维护p放的数字都要比q放的数字大
                priority_queue<int,vector<int>,greater<int>> big;
                for(int x=j;x<=j+len-1;x++){
                    // 如果此时小集合里面的数字更多
                    if(big.size()<sml.size()){
                        if(a[x]<sml.top()){
                            sml.push(a[x]);
                            big.push(sml.top());
                            sml.pop();
                        }else{
                            big.push(a[x]);
                        }
                    }else{
                        // 特判为空的情况
                        if(big.size()==0){
                            big.push(a[x]);
                            continue;
                        }
                        if(a[x]>big.top()){
                            big.push(a[x]);
                            sml.push(big.top());
                            big.pop();
                        }else{
                            sml.push(a[x]);
                        }
                    }
                }
                // 这里要特判长度为1的情况，否则会出现段错误
                if(len%2==0||len==1){
                    ans=max(ans,big.top());
                }else{
                    ans=max(ans,sml.top());
                }
            }
        }

        return ans;
    }
};

解法二 二分+双指针

• 首先，我们判断了其实最后的答案是有单调性的。所以我们可以先对区间进行排序。这样，我们就可以二分区间的长度了，然后，对于每个数字，我们用双指针维护，判断这个数字是否可能是中数。这里的维护我是先利用一个sum来维护一个满足大于等于区间中点的数字的个数前缀和，然后利用双指针扫，如果一旦发现符合条件的，那么直接返回。但是，双指针扫的时候需要注意挺多细节的，具体可以看我的代码实现。

• 代码如下

  • 二分的时间复杂度为,双指针维护的时间复杂度为。所以，总的时间复杂度为,这正好是符合题目的时间复杂度的。
  • 需要对序列进行存储，空间复杂度为

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int sum[100010];
    bool judge(int n,int k,vector<int>& a,int mid,int p){
        int ans=0;
        // 维护一个大于等于这个mid的前缀和，方便我们进行二分
        for(int i=0;i<n;i++){
            if(a[i]>=mid) sum[i+1]=sum[i]+1;
            else sum[i+1]=sum[i];
        }
        for(int l=0,r=0;l<n;l++){
            // 左边小于右边，同时这段之间大于等于mid的数字不超过区间一半，那么右指针继续遍历
            // 这里挺多细节的，请细细体会
            while(l==r||(l<=r&&r<n&&(r-l+1<k||(sum[r+1]-sum[l])*2<(r-l+1)))){
                r++;
            }
            // 判断是否存在
            if(r==n){
                if(r-l>=k&&(sum[r]-sum[l])*2>=(r-l+1)){
                    return true;
                }
            }else{
                 if(r-l+1>=k&&(sum[r+1]-sum[l])*2>=(r-l+1)){
                    return true;
                }
            }
        }
        return false;
    }
    int solve(int n, int k, vector<int>& a) {
        // write code here
        vector<int> b=a;
        sort(b.begin(),b.end());
        int l=0,r=b.size()-1,mid;
        int ans=b[r];
        // 二分符符合条件的数字所在的位置
        while(l<=r){
            mid=(l+r)>>1;
            if(judge(n,k,a,b[mid],mid)){
                l=mid+1;
                ans=b[mid]; // ans维护最后的答案
            }else{
                r=mid-1;
            }
        }
        return ans;
    }
};