mardi 14 juin 2022

find the longest consecutive segment l, r

given n numbers h[i] ( 1 <= i <= n ) and the number t is not negative find the longest consecutive segment l, r where every pair (i, j) with l <= i <= j <= r then abs(h[i] — h[j]) <= t

I think use binary search to find the answer and use deque to find min — max translation to check but it's wrong

please help me !!!!

////// this my code

bool check(int k){
        //if(k == 1) return 1;
        // find min
        vector<ll> min_h(n + 5, -1);
        deque<ll> q1;
        for(int i = 1; i <= n; i ++){
            while(q1.size() && a[q1.back()] >= a[i]) q1.pop_back();
            q1.push_back(i);
            if(q1.front() + k <= i) q1.pop_front();
            if(i >= k)min_h[i] = a[q1.front()];
        }
        
        // find max
        vector<ll> max_h(n + 5, -1);
        deque<ll> q2;
        for(int i = 1; i <= n; i ++){
            while(q2.size() && a[q2.back()] <= a[i]) q2.pop_back();
            q2.push_back(i);
            if(q2.front() + k <= i) q2.pop_front();
            if(i >= k)max_h[i] = a[q2.front()];
        }
        for(int i = k; i <= n; i ++)
            if(abs(max_h[i] - min_h[i]) <= t) return 1;
        return 0;
        
    }
    
    ll sol(){
        ll l = 1, r = n; 
        ll ans = -1;
        while(l <= r){
            ll mid = (l + r) / 2;
            if(check(mid)){
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        return ans;
    }

Aucun commentaire:

Enregistrer un commentaire