[アルゴリズム]int配列a[]は、すべてのa[i]を求め、左側はそれ以下、右側はそれ以上である.

2302 ワード


のように
a[]={7,9};
しゅつりょく
7,9
例えばa[]={7,10,2,6,19,22,32}である.
出力19,22,32
アルゴリズム:
簡単で、空間で時間を変えて、各要素の右側の区間の最小値を記録して、右に移動する時に左の最大値を更新して、もし現在の要素が右の最小値以下で、左の最大値以上であれば、条件に合って、出力します.
void foo(int a[], int n)
{
    if(n > 0)
    {
        int* rightMin = new int[n];
        int min = a[n-1],i;
        rightMin[n-1] = min;
        for(i = n-2; i >= 0; --i)
        {
            if(a[i] < min )
            {    
                min = a[i];
            }
            rightMin[i] = min;
        }
        int leftMax = a[0];
        for(i = 0; i < n; ++i)
        {
            if(a[i] >= leftMax && a[i] <= rightMin[i+1])
            {
                cout<<a[i]<<" ";
            }
        }
        delete[] rightMin;    
    }
        
}