Max Stack

class MaxStack {
    list<int> lst;
    map<int, vector<list<int>::iterator>> mp;
public:
    void push(int x) {
        lst.push_back(x);
        mp[x].push_back(prev(lst.end()));
    }
    int pop() {
        int x = lst.back();
        mp[x].pop_back();
        if (mp[x].empty()) mp.erase(x);
        lst.pop_back();
        return x;
    }
    int top() { return lst.back(); }
    int peekMax() { return mp.rbegin()->first; }
    int popMax() {
        int x = mp.rbegin()->first;
        auto it = mp[x].back();
        mp[x].pop_back();
        if (mp[x].empty()) mp.erase(x);
        lst.erase(it);
        return x;
    }
};

import (
    "container/list"
    "sort"
)

type MaxStack struct {
    lst  *list.List
    mp   map[int][]*list.Element
    keys []int // sorted ascending, distinct
}

func Constructor() MaxStack {
    return MaxStack{lst: list.New(), mp: map[int][]*list.Element{}}
}

func (s *MaxStack) addKey(x int) {
    i := sort.SearchInts(s.keys, x)
    if i < len(s.keys) && s.keys[i] == x {
        return
    }
    s.keys = append(s.keys, 0)
    copy(s.keys[i+1:], s.keys[i:])
    s.keys[i] = x
}

func (s *MaxStack) removeKey(x int) {
    i := sort.SearchInts(s.keys, x)
    if i < len(s.keys) && s.keys[i] == x {
        s.keys = append(s.keys[:i], s.keys[i+1:]...)
    }
}

func (s *MaxStack) Push(x int) {
    e := s.lst.PushBack(x)
    if _, ok := s.mp[x]; !ok {
        s.addKey(x)
    }
    s.mp[x] = append(s.mp[x], e)
}

func (s *MaxStack) Pop() int {
    e := s.lst.Back()
    x := e.Value.(int)
    s.mp[x] = s.mp[x][:len(s.mp[x])-1]
    if len(s.mp[x]) == 0 {
        delete(s.mp, x)
        s.removeKey(x)
    }
    s.lst.Remove(e)
    return x
}

func (s *MaxStack) Top() int { return s.lst.Back().Value.(int) }

func (s *MaxStack) PeekMax() int { return s.keys[len(s.keys)-1] }

func (s *MaxStack) PopMax() int {
    x := s.keys[len(s.keys)-1]
    es := s.mp[x]
    e := es[len(es)-1]
    s.mp[x] = es[:len(es)-1]
    if len(s.mp[x]) == 0 {
        delete(s.mp, x)
        s.removeKey(x)
    }
    s.lst.Remove(e)
    return x
}

from sortedcontainers import SortedList

class MaxStack:
    def __init__(self) -> None:
        self.stack: SortedList = SortedList()
        self.values: SortedList = SortedList()
        self.cnt = 0

    def push(self, x: int) -> None:
        self.stack.add((self.cnt, x))
        self.values.add((x, self.cnt))
        self.cnt += 1

    def pop(self) -> int:
        i, x = self.stack.pop()
        self.values.remove((x, i))
        return x

    def top(self) -> int:
        return self.stack[-1][1]

    def peekMax(self) -> int:
        return self.values[-1][0]

    def popMax(self) -> int:
        x, i = self.values.pop()
        self.stack.remove((i, x))
        return x

class MaxStack {
    constructor() {
        this.stack = [];
        this.maxStack = [];
    }

    push(x) {
        this.stack.push(x);
        const curMax = this.maxStack.length === 0 ? x : this.maxStack[this.maxStack.length - 1];
        this.maxStack.push(Math.max(curMax, x));
    }

    pop() {
        this.maxStack.pop();
        return this.stack.pop();
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    peekMax() {
        return this.maxStack[this.maxStack.length - 1];
    }

    popMax() {
        const max = this.peekMax();
        const buffer = [];
        while (this.top() !== max) buffer.push(this.pop());
        this.pop();
        while (buffer.length) this.push(buffer.pop());
        return max;
    }
}

class MaxStack {
    private Deque<Integer> stack;
    private Deque<Integer> maxStack;

    public MaxStack() {
        stack = new ArrayDeque<>();
        maxStack = new ArrayDeque<>();
    }

    public void push(int x) {
        stack.push(x);
        int curMax = maxStack.isEmpty() ? x : Math.max(maxStack.peek(), x);
        maxStack.push(curMax);
    }

    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Deque<Integer> buffer = new ArrayDeque<>();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

class MaxStack {
    private stack: number[];
    private maxStack: number[];

    constructor() {
        this.stack = [];
        this.maxStack = [];
    }

    push(x: number): void {
        this.stack.push(x);
        const curMax = this.maxStack.length === 0 ? x : this.maxStack[this.maxStack.length - 1];
        this.maxStack.push(Math.max(curMax, x));
    }

    pop(): number {
        this.maxStack.pop();
        return this.stack.pop()!;
    }

    top(): number {
        return this.stack[this.stack.length - 1];
    }

    peekMax(): number {
        return this.maxStack[this.maxStack.length - 1];
    }

    popMax(): number {
        const max = this.peekMax();
        const buffer: number[] = [];
        while (this.top() !== max) buffer.push(this.pop());
        this.pop();
        while (buffer.length) this.push(buffer.pop()!);
        return max;
    }
}