Push, Pop, Диапазон в постоянное время

Question

меня спросили в интервью:

дизайна структура данных, которая позволяет все эти операции в постоянном, O(1), время:

• вытолкнуть элемент
• Поп-элемент
• Диапазон элементов: найдите наименьший диапазон интервалов текущих элементов.
  Например. Диапазон [1, 22, 44, 56, 99, 98, 56] - 98.

Я разработал это, используя пользовательский стек с двумя переменными, max и min, но это не работает после Pop'ing на мин или макс элемент.

Что я пробовал:

Я использовал стек с двумя дополнительными переменной макс и мин:

DS 
{ 
top, //Top of the Stack 
min, //Min till now 
max //Max till now 
} 

Push(DS, elem) 
    Push_Stack(DS.top, elem) 
    if elem < DS.min 
    DS.min = elem 
    if elem > DS.max 
    DS.max = elem 

Range(DS) 
return DS.max - DS.min 

Pop(DS) 
    x = Pop_Stack(DS.top) 
    if (x == DS.min) 
    DS.min = Find_New_Min(DS.top) //This takes linear time using this approach 
    if (x == DS.max) 
    DS.max = Find_New_Max(DS.top) 

Answer 1

Реализовать «Стек», который включает в себя функцию диапазона и использует три стеки внутри.

---

Первый внутренний стек будет представлять собой «реальную» стопку вещей, которые толкаются и выталкиваются.

Второй внутренний стек будет перенесен только в том случае, если новый элемент больше или равен тому, что находится поверх него.

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

---

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

Всякий раз, когда элемент нужно выталкивать из «реального» стека, проверьте, находится ли этот элемент также в верхней части каждого из двух других стеков, если он есть, выскочите с этих стеков.

Поскольку вы должны вытаскивать предметы из главного стека в обратном порядке, они вошли, вы никогда не пропустите ничего в двух других столах ... что означает, что верхняя часть второго и третьего внутренних стеков всегда будет макс и мин.

Answer 2

Это похоже на Bryon Lo ответ, но прежде чем он отправил I commented same

Поддерживайте 3 стака

• S1 ваши конечные стеки
• S2 и S3 временные стеки

Отдых является само собой разумеющимся

push(T value) 
    { 
    if (value <= min()) 
    { 
     s2.push(value); 
    } 

    if(value >= max()) 
    { 
     s3.push(value); 
    } 
    s1.push(value); 
    } 

T pop() 
{ 
    T value = s1.pop(); 
    if (value == min()) 
    { 
     s2.pop(); 
    } 
    return value; 
    } 

    T min() 
    { 
    if (s2.isEmpty()) 
    { 
     return MAX_VALUE; 
    } 
    else { 
     return s2.peek(); 
    } 
    } 

    T max() 
    { 
    if (s3.isEmpty()) 
    { 
     return MIN_VALUE; 
    } 
    else 
    { 
     return s3.peek(); 
    } 
    }