python - 堆栈和优化 - 来自 hackerrank 的示例

Question

我有一个关于 Python 堆栈的问题。我试图解决 Maximum Element Hackerrank 中的任务:

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

为了解决这个问题，我写了这样的东西:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def maxEl(self):
        return max(self.items)


s = Stack()   

for i in range(int(input())):
    n = input().split()

    if n[0] == '1':
        s.push(int(n[1]))
    elif n[0] == '2':
        s.pop()
    else:
        print(s.maxEl())

它有效，但显然太慢了，我只通过了 28 个测试用例中的 18 个(因为超时)。我找到了类似的解决方案，而且速度足够快，但我不明白为什么:

class Stack:
    def __init__(self):
        self.arr = [0]
        self.max = [0]

    def push(self, data):
        self.arr.append(data)
        if self.max[-1] <= data:
            self.max.append(data)

    def pop(self):
        if self.arr[-1] == self.max[-1]:
            self.max.pop()
        self.arr.pop()


N = int(input())
s = Stack()

for _ in range(N):
    x = str(input())

    if x[0] == '1':
        s.push(int(x[2:]))

    elif x[0] == '2':
        s.pop()

    else:
        print(s.max[-1])

有人能解释一下为什么我的代码性能不佳吗？谢谢。

Answer 1

这两个解决方案非常相似，除了返回堆栈中最大元素的代码。

在您的解决方案中，您使用了 max() 函数:

def maxEl(self):
    return max(self.items)

这在 O(n) 时间内运行，因为 max() 必须在最坏情况下检查每个元素。

在另一个解决方案中，最大值存储在另一个堆栈中，因此获取当前最大值只是一个索引操作，它在 O(1) 时间内运行:

s.max[-1]

在每次推送/弹出时更新最大值堆栈也有一些成本，但这些操作仍然是 constant time .