ロープで覆うことができる最大点数

668 ワード

あるネットユーザーは、私のアルゴリズムは実際に余分な配列を申請する必要はありません.では、より効率的なアルゴリズムはありませんか.私の周りの大神は私にO(N)複雑度のアルゴリズムをくれました.
彼の原話:2つのポインタ、1つのfront、1つのrear、毎回front-rear、Lより小さくて、カバーする点数を見ます.上書き点数の最大値を保存しfront++;Lよりも大きく、rear++であり、各数は最大2回、複雑度O(N)である.
このアルゴリズムに対して、彼はイメージの比喩を与えた.
まるで長さLの蛇のようだ.頭が伸ばせない場合は、尻尾を縮めて最大1回歩くだけで、いくつかの点をカバーできることがわかります
int line(int a[],int n,int len)
{
    int front,rear,maxnum;
    front = rear = maxnum = 0;

    while(front < n)
    {
        if(a[front] - a[rear] <= len)
        {
            maxnum = fmax(maxnum,front-rear);
            front++;
        }
        else
            rear++;
    }
    return maxnum+1;
}