Следующее решение использует O (1) дополнительную память и O (1) время для операций max, push и pop.
Сохраняйте переменную max, которая будет отслеживать текущий элемент max в любой конкретный момент времени.
Давайте используем тот факт, что при обновлении max все элементы в стеке должны быть меньше, чем новый элемент max.
Когда происходит операция push и новый элемент (newElement) больше текущего max, мы помещаем max + newElement в стек и обновляем max = newElement.
Когда мы выполняем операцию pop и обнаруживаем, что текущий вытолкнутый элемент больше текущего max, тогда мы знаем, что это место, где мы обновили наш стек, чтобы он содержал max + elem. Таким образом, фактический элемент, который должен быть возвращен, это max, а max = poppedElem - max.
Например. если мы нажимаем 1, 2, 3, 4, 5, переменная stack и max будет выглядеть следующим образом:
MAIN Value of MAX
+---+ +---+
| 9 | max = | 5 |
| 7 | max = | 4 |
| 5 | max = | 3 |
| 3 | max = | 2 |
| 1 | max = | 1 |
+---+ +---+
Теперь допустим, что мы вытолкнули элемент, мы в основном вытолкнем элемент max (поскольку top> max) и обновим элемент max до (top-max)
MAIN Value of MAX
+---+ +---+
| 7 | max = | 4 | = (9-5)
| 5 | max = | 3 |
| 3 | max = | 2 |
| 1 | max = | 1 |
+---+ +---+
Теперь предположим, что мы нажимаем цифры 5, 4, 3, 2, 1, стек будет выглядеть так:
MAIN Value of MAX
+---+ +---+
| 1 | max = | 5 |
| 2 | max = | 5 |
| 3 | max = | 5 |
| 4 | max = | 5 |
| 5 | max = | 5 |
+---+ +---+
Когда мы выталкиваем, вершина стека выталкивается, так как top
Ниже приведен псевдокод для каждой операции для лучшего понимания.
Elem max;
void Push(Elem x){
if x < max :
push(x);
else{
push(x+max);
max = x;
}
}
Elem Pop(){
Elem p = pop();
if |p| < |max|:
return p;
else{
max = p - max;
return max;
}
}
Elem Max(){
return max;
}
push и pop - обычные операции со стеком. Надеюсь, это поможет.