Какова будет структура данных в следующем сценарии? (Stack with maximum)

Question

Обратите внимание, что ограничений по памяти нет. мне нужно вставить Int от 1 до 1000.

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

1. нажимной(): добавляет к началу
2. поп(): удаляет верхний элемент
3. getMax(): возвращает максимальный элемент

Пожалуйста, предложите мне подходящую структуру данных.

Answer 1

Поскольку нет ограничений на память, я буду использовать 2 вектора - один для фактических данных в стеке, а другой для отслеживания max в каждом состоянии стека.
Для простоты я предполагаю, что этот стек содержит только + ve ints.
Я знаю, что это не проверка ошибок. Но я просто предлагаю идею структуры данных здесь, а не полноценное решение.

class StackWithMax 
{ 
public: 
    StackWithMax() : top(-1), currentMax(0) { } 
    void push(int x); 
    int pop(); 
    int getMax() { return m[top]; } 
private: 
    vector<int> v; // to store the actual elements 
    vector<int> m; // to store the max element at each state 
    int top; 
    int currentMax; 
}; 

void StackWithMax::push(int x) 
{ 
    v[++top] = x; 
    m[top] = max(x, currentMax); 
} 

int StackWithMax::pop() 
{ 
    int x = v[top--]; 
    currentMax = m[top]; 
    return x; 
} 

Answer 2

Используйте обычную структуру стека и дополнительный массив для счетчиков int c[1..1000] и переменной int maxVal=0.

В коде добавить действий после операций стеки:

On push(x) -> c[x]++ ; maxVal = max(x,maxVal) 
On pop():x -> c[x]-- ; if (c[x] == 0) { j=x; while(c[--j] == 0); maxVal = j; } 

MAXVAL должен всегда максимальное значение.

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