Как определить экстремумы (min & max) динамического интервала

Question

У меня есть массив длиной 200. Каждую секунду у меня есть новый номер, добавленный в позицию [0] массива, нажимая другие значения на одну позицию в массиве.

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

Мне это удалось, но я столкнулся с некоторыми проблемами, отбрасывая «старый» макс и «старый» мин, поскольку, как только они вытесняются из массива, я больше их не нуждаюсь.

Я нашел способ сделать это, используя 1-й дифференциал и нажав фактическое значение в другой массив. Проблема заключалась в том, что когда у меня есть мин или макс, появляющиеся несколько раз. Этот новый массив заставил бы их повторять в определенном порядке, и мне нужен всего один макс и один мин.

Answer 1

Если у вас есть массив из n значений, которые обновляются с интервалом путем удаления первого элемента и нажатия нового в конце, вы можете разбить алгоритм, который находит min/max интервала в два этапа.

Ваше предварительное условие позволяет сделать сильное предположение, которое является тот факт, что

min(data) = min(data[0], data[1..n-1]) 

Начиная с этого предположения вам не нужно вычислить мин/макс на всех значений на каждом шаге.

Давайте сделаем пример, предположим, что вы сказали, чтобы иметь 200 значений и иметь общую функцию min, способную вычислять минимум массива, пару значений или значение и массив. Это метакод, игнорируйте синтаксис.

Вы начинаете, предварительно рассчитав минимум и дополнительные данные поддержки:

int middleMin = min(array[1..n-1]); // so we skip first 
int firstValue = array[0]; 
int realMin = min(firstValue, middleMin); 

Теперь, когда вы вставляете новый элемент в конце и удалить первые две вещи, которые могут произойти:

• firstValue == realMin (&& firstValue < middleMin), в этом случае вы должны найти следующее более высокое значение на новом array[0..n-1], так как вы удалили минимум
• middleMin == realMin, в этом случае вы знаете, что удаленный элемент был не первым, поэтому вам не нужно перекомпилировать глобальный минимум, вам просто нужно его обновить в соответствии с новым вставленным элементом, например middleMin = realMin = min(realMin, array[n-1])
• На самом деле также может случиться так, что firstValue == middleMin, но это относится ко второму случаю, поскольку в массиве трейлов есть еще одно значение, которое является текущим минимумом.