Структура данных, которая поддерживает поиск максимального числа между 2 индексами в O (1)

Question

Мне задали следующий вопрос:

Учитывая массив из n различных чисел, разработайте структуру данных, которая поддерживает поиск максимального числа за интервал (который задается 2 индексами - верхняя и нижняя границы) с O (1) временной сложностью.

Так, например, если заданы индексы i,j (такие, что i Max(A[i],A[i+1],…,A[j]) в O (1) сложности времени. (другими словами, учитывая i,j, мне нужно выяснить, какое из следующих чисел является наибольшим: A [i], A [i + 1],…, A [j]) Время инициализации, допустимое для структуры данных, равно O (n ^ 2). Других ограничений нет.

Я выдвинул несколько идей, но я не мог придумать что-то прямолинейное, и было доказано, что оно соответствует требованиям.

Помощь оценена.

Answer 1

Чтобы решить эту проблему, нужно создать массив nxn и заполнить этот массив ответом для каждого [i,j]. Общая идея:

a[] // this is the input array
results = new [n,n]

// this is the same loop structure used for selection sort
for (i = 0; i < n-1; ++i)
{
    largest = a[i]
    results[i,i] = largest
    for (j = i+1; j < n; ++j)
    {
        if (a[j] > largest)
        {
            largest = a[j]
        }
        results[i,j] = largest
     }
}

Учитывая массив [1, 2, 5, 3, 4], который должен создать:

1, 2, 5, 5, 5
?, 2, 5, 5, 5
?, ?, 5, 5, 5
?, ?, ?, 3, 4
?, ?, ?, ?, 4

Знак вопроса означает, что нам все равно, какие там значения. Если вас спросят значения i и j, вы просто посмотрите вверх results[i,j] и получите ответ. Потому что i < j, вы никогда не будете индексировать ячейки с вопросительными знаками.

Таким образом, время инициализации равно O (n ^ 2), а необходимое пространство равно O (n ^ 2).

Answer 2

Может быть, что-то подобное будет работать? Вы помните самые большие и самые маленькие числа, когда они добавляются в массив, поэтому, когда вас запрашивают ответ для максимального диапазона, вы уже знаете его (т. Е. O (1))

class SmartArray{
   innerArray=[];
   smallest;
   largest;

   //There are edge cases here when the array is 
   //0 or 1 elements that you might have to work out
   add(element){
      innerArray.add(element);
      if(element>largest){
         largest=element
      }
      if(element<smallest){
         smallest=element
      }
   }

   //Definitely O(1)
   getMaxNumber(){
      return largest-smallest;
   }

}