Учитывая массив A [] из N натуральных чисел. Задача состоит в том, чтобы найти максимум j - i, на который наложено ограничение A [i] <= A [j]. </p>
Входные данные: первая строка содержит целое число T, отображающее общее количество тестовых случаев. Затем следует Т-тест. Первая строка каждого теста содержит целое число N, обозначающее размер массива. Следующая строка содержит N разделенных пробелом целых чисел, обозначающих элементы массива.
Выходные данные: Выведите максимальную разницу индексов i и j в отдельной строке.
Ограничения: 1 ≤ T ≤ 1000 1 ≤ N ≤ 107 0 ≤ A [i] ≤ 1018
Пример: ввод: 1 9 34 8 10 3 2 80 30 33 1
вывод: 6
I написал решение для O (n). Но я получаю ошибку «превышено ограничение по времени» при отправке этого решения.
Чтобы решить эту проблему, нам нужно получить два оптимальных индекса arr []: левый индекс i и правый индекс j. Для элемента arr [i] нам не нужно рассматривать arr [i] для левого индекса, если в левой части arr [i] есть элемент меньше, чем arr [i]. Аналогично, если в правой части arr [j] есть больший элемент, нам не нужно рассматривать этот j для правильного индекса. Таким образом, мы строим два вспомогательных массива min [] и max [] так, чтобы min [i] содержал наименьший элемент в левой части arr [i], включая arr [i], а max [j] содержал наибольший элемент в правой части arr [j], включая arr [j]. После построения этих двух вспомогательных массивов мы пересекаем оба этих массива слева направо. Обходя min [] и max [], если мы видим, что min [i] больше max [j], то мы должны двигаться вперед в min [] (или делать i ++), потому что все элементы слева от min [i] больше или равно min [i]. В противном случае мы должны двигаться вперед в max [j], чтобы найти большее значение j - i
Можем ли мы его оптимизировать больше?
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main (String[] args) {
Scanner in =new Scanner(System.in);
int noOfUsecases=in.nextInt();
for(int i=0;i<noOfUsecases;i++){
int arrayLength=in.nextInt();
int[] arr=new int[arrayLength];
if(in.hasNextInt()){
for(int j=0;j<arrayLength;j++){
arr[j]=in.nextInt();
}
}
maximumIndex(arr,arrayLength);
}
}
public static void maximumIndex(int[] arr,int length){
int i = 1,j = length-2;
int maxDiff=0;
int[] min=new int[length];
min[0]=arr[0];
for(;i<length;++i){
min[i]=arr[i]<min[i-1]?arr[i]:min[i-1];
}
int[] max=new int[length];
max[length-1]=arr[length-1];
for(;j>=0;--j){
max[j]=arr[j]>max[j+1]?arr[j]:max[j+1];
}
i = 0;j = 0;
while (j < length && i < length)
{
if (min[i] <= max[j])
{
maxDiff = maxDiff>(j - i)?maxDiff:(j-i);
j = j + 1;
}
else
i = i + 1;
}
System.out.println(maxDiff);
}}