Description
Given \ (n \), \ (k \) and a sequence with a length of \ (n \), find the longest maximum value and the sub segment with a minimum value difference of no more than \ (k \).
Constraints
\(0 \le k \le 2*10^9\)，\(1 \le n \le 3*10^6\)
Solution 1
Consider violence.
Violence enumerates the length of the last answer, and then violence looks for it.
Time complexity \ (O(n^3) \), timeout.
Solution 2
It is found that the final answer satisfies the dichotomy.
The length of the final answer is divided into two parts. After the interval is fixed, it is similar to the question of sliding window. The monotonic queue is used to maintain the maximum and minimum values in the interval.
The time complexity is \ (O(nlogn) \), because \ (n \) is large, a point may be stuck if the constant is too large.
Code
// by youyou2007 in 2022
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#define REP(i, x, y) for(int i = x; i < y; i++)
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define PER(i, x, y) for(int i = x; i > y; i--)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define lc (k << 1)
#define rc (k << 1 | 1)
using namespace std;
const int N = 3E6 + 5;
int n, k;
int a[N];
int low, mid, high, ans = 0;
int qmin[N], qmax[N];
bool check(int kk)//Judge whether the length is mid is feasible
{
int sum = 0x3f3f3f3f;
int minhead = 1, mintail = 0, maxhead = 1, maxtail = 0;
qmin[mintail] = 1, qmax[maxtail] = 1;
rep(i, 1, n)
{
while(minhead <= mintail && qmin[minhead] <= i - kk)//If the queue header element exceeds the range, it needs to pop up from the front of the queue
{
minhead++;
}
while(maxhead <= maxtail && qmax[maxhead] <= i - kk)//The maximum value is the same
{
maxhead++;
}
while(minhead <= mintail && a[qmin[mintail]] >= a[i])//If the end of the queue element is greater than or equal to $a[i] $in the queue maintaining the minimum value, it means that $a[i] $is smaller and the position is closer to the back, which must be better
{
mintail--;
}
while(maxhead <= maxtail && a[qmax[maxtail]] <= a[i])
{
maxtail--;
}
qmin[++mintail] = i;
qmax[++maxtail] = i;
if(i >= kk)
{
if(a[qmax[maxhead]] - a[qmin[minhead]] <= k) return 1;As long as any section can be found to meet the maximum and minimum value, the difference shall not exceed k，Then there is a solution
}
}
// cout << kk<<" " << sum<<endl;
return 0;
}
int main()
{
scanf("%d%d", &k, &n);
rep(i, 1, n)
{
scanf("%d", &a[i]);
}
low = 0, high = n;
while(low <= high)
{
// cout << low << " " << high << endl;
mid = (low + high) / 2;
if(check(mid) == 1)//If mid is feasible, look to the right half
{
ans = mid;
low = mid + 1;
}
else//Otherwise, look to the left half
{
high = mid - 1;
}
}
printf("%d", ans);
return 0;
}
Solution 3
The last algorithm is too personal and needs to be optimized
It is found that instead of determining the answer length first, we can find it when maintaining a monotonous queue
Consider maintaining two monotone queues, which respectively maintain the subsequence with no rise (maximum value) and no fall (minimum value) ending with \ (a[i] \), and the subscript of each number in the subsequence
At each position, judge whether the difference between the corresponding values of the subscripts of the two queue heads is greater than K. if it is greater than k, pop up the queue heads in the front of the two queues (in order to keep the legal interval as large as possible) until the difference \ (≤ K \).
Then update the left end point of the legal sequence, which is the next position after the pop-up position. Update the maximum sequence length every time.
It is also easy to understand why the maximum maintenance value that does not rise and the minimum maintenance value that does not fall should be used:
If the current interval difference is too large, it indicates that the maximum value is too large or the minimum value is too small. In order to reduce the difference, you can reduce the maximum value or expand the minimum value. Therefore, the queue maintains elements that can narrow the difference.
Time complexity \ (O(n) \).
Code:
// by youyou2007 in 2022
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#define REP(i, x, y) for(int i = x; i < y; i++)
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define PER(i, x, y) for(int i = x; i > y; i--)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define lc (k << 1)
#define rc (k << 1 | 1)
using namespace std;
const int N = 3e6 + 5;
int n, a[N], k;
int qmax[N], qmin[N];
int l = 1, ans = 1;//l represents the left end point of the current interval. The answer ans from here must be 1, otherwise an error will occur when n=1!
int headmax = 1, tailmax = 1, headmin = 1, tailmin = 1;//There will be a number in the queue at the beginning
int main()
{
scanf("%d%d", &k, &n);
rep(i, 1, n)
{
scanf("%d", &a[i]);
}
qmax[1] = 1;
qmin[1] = 1;
rep(i, 2, n)
{
while(headmax <= tailmax && a[qmax[tailmax]] < a[i]) tailmax--;//The maximum value, but the sub segment that does not rise is maintained
while(headmin <= tailmin && a[qmin[tailmin]] > a[i]) tailmin--;//The minimum value is maintained for the sub segment that does not descend
qmin[++tailmin] = i;
qmax[++tailmax] = i;
while(a[qmax[headmax]] - a[qmin[headmin]] > k)//If the difference is greater than k, the interval shall be continuously reduced
{
if(qmax[headmax] < qmin[headmin])//If the position of the team head maintaining the maximum value is ahead, it indicates that priority is given to reducing the maximum value
{
l = qmax[headmax] + 1; //Update the left endpoint. Since the position of the maximum value is illegal, it will be legal after it, so it is the position of the maximum value + 1
headmax++;//Pop up the head of the team
}
else//And vice versa
{
l = qmin[headmin] + 1;
headmin++;
}
}
ans = max(ans, i - l + 1);//The maximum interval length shall be updated once at each position
}
printf("%d", ans);
return 0;
}