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

Question

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

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

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

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

Answer 1

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

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). Прошло много времени с тех пор, как я анализировал алгоритмы.