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