716. 最大栈
设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。
实现 MaxStack 类：
MaxStack() 初始化栈对象
void push(int x) 将元素 x 压入栈中。
int pop() 移除栈顶元素并返回这个元素。
int top() 返回栈顶元素，无需移除。
int peekMax() 检索并返回栈中最大元素，无需移除。
int popMax() 检索并返回栈中最大元素，并将其移除。如果有多个最大元素，只要移除 最靠近栈顶 的那个。
示例：
输入
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
输出
[null, null, null, null, 5, 5, 1, 5, 1, 5]
解释
MaxStack stk = new MaxStack();
stk.push(5); // [5] - 5 既是栈顶元素，也是最大元素
stk.push(1); // [5, 1] - 栈顶元素是 1，最大元素是 5
stk.push(5); // [5, 1, 5] - 5 既是栈顶元素，也是最大元素
stk.top(); // 返回 5，[5, 1, 5] - 栈没有改变
stk.popMax(); // 返回 5，[5, 1] - 栈发生改变，栈顶元素不再是最大元素
stk.top(); // 返回 1，[5, 1] - 栈没有改变
stk.peekMax(); // 返回 5，[5, 1] - 栈没有改变
stk.pop(); // 返回 1，[5] - 此操作后，5 既是栈顶元素，也是最大元素
stk.top(); // 返回 5，[5] - 栈没有改变
提示：
- 107 <= x <= 107 最多调用 104 次 push、pop、top、peekMax 和 popMax 调用 pop、top、peekMax 或 popMax 时，栈中 至少存在一个元素
进阶：
- 试着设计解决方案：调用 top 方法的时间复杂度为 O(1) ，调用其他方法的时间复杂度为 O(logn) 。
有序列表
思路
python 有序字典+有序集合
设一个自增的 id 标记每个元素 x，有序字典按 push 顺序维护 <id,x>，有序集合按大小顺序维护 <x, id>。
pop 和 popMax 操作时，注意在有序字典和有序集合同步删除即可。
单个操作时间复杂度 O(logN)。
题解
from sortedcontainers import SortedList class MaxStack: def __init__(self): self.s = SortedList() self.d = OrderedDict() self.idx = 0 def push(self, x: int) -> None: self.d[self.idx] = x self.s.add((x, self.idx)) self.idx += 1 def pop(self) -> int: idx, x = self.d.popitem() self.s.remove((x, idx)) return x def top(self) -> int: return next(reversed(self.d.values())) def peekMax(self) -> int: return self.s[-1][0] def popMax(self) -> int: x, idx = self.s.pop() self.d.pop(idx) return x # Your MaxStack object will be instantiated and called as such: # obj = MaxStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.peekMax() # param_5 = obj.popMax()