0716：最大栈（★★）

力扣第 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) 。 

分析

• 有序集合维护最大元素及其在栈中的位置
• 用 OrderdDict 模拟双向链表，弹出元素即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class MaxStack:

    def __init__(self):
        from sortedcontainers import SortedList
        self.sl = SortedList()
        self.d = OrderedDict()
        self.id = 0

    def push(self, x: int) -> None:
        self.d[self.id] = x
        self.sl.add((x, self.id))
        self.id += 1

    def pop(self) -> int:
        id, x = self.d.popitem()
        self.sl.remove((x, id))
        return x

    def top(self) -> int:
        return next(reversed(self.d.values()))

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

    def popMax(self) -> int:
        x, id = self.sl.pop()
        self.d.pop(id)
        return x

132 ms