时间戳

首页 > 解决方案 > 堆栈和优化——来自hackerrank的例子

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

问题描述

我有一个关于 Python 中的堆栈的问题。我试图解决Hackerrank 中的最大元素任务：

您有一个空序列，您将收到 N 个查询。每个查询都是以下三种类型之一：

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.

输入的第一行包含一个整数 N。接下来的 N 行每行包含一个上述查询。（保证每个查询都是有效的。）

为了解决它，我写了这样的东西：

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])

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

标签： pythonstack

解决方案

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

在您的解决方案中，您使用以下max()功能：

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

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

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

s.max[-1]

每次推送/弹出时更新最大值堆栈也有一些成本，但这些操作仍然是常数时间。

推荐阅读