爆刷PAT（甲级）——之【1101】 Quick Sort (25 分)——简单思维

最新推荐文章于 2022-10-29 12:44:43 发布

仰天倀笑

最新推荐文章于 2022-10-29 12:44:43 发布

阅读量303

点赞数 2

分类专栏： # PAT甲级【爆刷】文章标签： 1101 Quick Sort (25 分) 爆刷PAT（甲级）简单思维算法题简单入门编程题 C++算法题

本文链接：https://blog.csdn.net/Hide_in_Code/article/details/100050513

版权

PAT甲级【爆刷】专栏收录该内容

35 篇文章

订阅专栏

本文介绍了一种算法，用于从无序正数数组中找到所有左侧元素小于它且右侧元素大于它的特殊元素。通过构建两个辅助数组，分别记录每个位置左侧的最大值和右侧的最小值，实现了高效查找。文章详细解释了算法思路，并提供了C++代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：给一个无序的正数数组（各数不同），找出，所有左边的数小于它，所有右边的数大于它，的数。输出符合条件的数，以及其个数。

思路：一下子就可以想到，所有左边的数小于它，那就是左边最大的数都比它小。

所有右边的数都大于它，那就是右边最小的数都比它大。即可。

所以什么操作都不需要，直接两个O（N），建立两个数组 l[i] 和 r[i] ，表示 i 下标位置左边最大的数和右边最小的数，扫一遍就建立好了。

然后每个点判断一边，如果元素比它左边一格的 l[i-1]都大，那就符合第一个条件；如果元素比它右边一格的 r[i+1] 都大，就符合第二个条件。都符合就加入vector最后排个序输出即可。

坑点：

两个坑爹之处——N小于等于10e5，数组别开小了；答案可能为0，但是输出还要输出一个'\n'，不然会PLE.

Code：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define inf 100009
#define INF 0x3f3f3f3f
#define loop(x,y,z) for(x=y;x<z;x++)

int n;
int e[inf];
int l[inf];//find max
int r[inf];//find min
vector<int>ans;//the ans

int main()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)scanf("%d",&e[i]);
    l[0]=0;
    r[n+1]=INF;
    for(i=1;i<=n;i++)l[i]=max(l[i-1],e[i]);
    for(i=n;i>0;i--)r[i]=min(r[i+1],e[i]);
    //判断
    for(i=1;i<=n;i++)
        if(e[i]>l[i-1]&&e[i]<r[i+1])
            ans.push_back(e[i]);
    sort(ans.begin(),ans.end());
    printf("%d\n",ans.size());
    if(!ans.size()){printf("\n");return 0;}//本题目最骚的地方
    for(i=0;i<ans.size()-1;i++)printf("%d ",ans[i]);
    printf("%d\n",ans[i]);
    return 0;
}