牛客编程巅峰赛S2第2场 - 钻石&王者 C-数据分析

C 数据分析

分析

1. 先看题目：最大的最小。其在做这一类的题都有一种思想。因为暴力时直接枚举区间，但是反着来，求出一个数对某一段区间的影响，拿样例举例
   
   一个数能作为最大值，区间的范围之内就不能出现大于它的任何数,设

   lm[i]:位于i左边第一个大于a[i]的数的位置+1
   rm[i]:位于i右边第一个大于a[i]的数的位置-1

   那么这个数能作为最大值的区间就出来了， ,而这里面的区间长度就是,也就是说，我们要在这个范围之内维护一个最小值，最后进行单点查询即可

代码

class Solution {
public:
    /**
     * 找到所有长度子数组中最大值的最小值
     * @param numbers int整型vector 牛牛给出的数据
     * @return int整型vector
     */
    #define ls now<<1
    #define rs now<<1|1

    int n,tp;
    int a[100005],lm[100005],rm[100005],stk[100005],tag[400005],s[400005];

    vector<int>ans;

    inline void pd(int now)
    {
        if(tag[now]>1e9) return ;
        tag[ls]=min(tag[ls],tag[now]);
        tag[rs]=min(tag[rs],tag[now]);
        s[ls]=min(s[ls],tag[now]);
        s[rs]=min(s[rs],tag[now]);
        tag[now]=0x3f3f3f3f;
        return ;
    }

    inline void ch(int now,int l,int r,int x,int y,int z)
    {
        if(l>=x&&r<=y)
        {
            s[now]=min(s[now],z);
            tag[now]=min(tag[now],z);
            return ;
        }pd(now);

        int mid=(l+r)>>1;
        if(x<=mid) ch(ls,l,mid,x,y,z);
        if(mid<y) ch(rs,mid+1,r,x,y,z);
        s[now]=min(s[ls],s[rs]);
    }

    inline int find(int now,int l,int r,int x)
    {
        if(l==r) return s[now];
        pd(now);

        int mid=(l+r)>>1;
        if(x<=mid) return find(ls,l,mid,x);
        return find(rs,mid+1,r,x);
    }

    vector<int> getMinimums(vector<int>& numbers) {
        // write code here
        n=numbers.size();
        for (int i=0;i<n;i++) a[i+1]=numbers[i];
        memset(s,0x3f,sizeof(s));
        memset(tag,0x3f,sizeof(tag));

        lm[1]=1;stk[++tp]=1;
        for (int i=2;i<=n;i++)
        {
            while(tp&&a[stk[tp]]<=a[i]) tp--;
            lm[i]=stk[tp]+1;
            stk[++tp]=i;
        }
        tp=0;stk[++tp]=n;stk[0]=n+1;
        rm[n]=n;
        for (int i=n-1;i>=1;i--)
        {
            while(tp&&a[stk[tp]]<=a[i]) tp--;
            rm[i]=stk[tp]-1;
            stk[++tp]=i;
        }

        for (int i=1;i<=n;i++)
            ch(1,1,n,1,rm[i]-lm[i]+1,a[i]);

        for (int i=1;i<=n;i++)
            ans.push_back(find(1,1,n,i));

        return ans;
    }
};

后话

因为我有一种打完比赛想立即看到解法的冲动，所以很快便写下了这篇题解造福他人，不甚详明，如有疑问，还请提出