时间戳

首页 > 解决方案 > Hackerrank 问题在时间限制内不适用于大数据（打印最大元素的堆栈问题）

python-3.x - Hackerrank 问题在时间限制内不适用于大数据（打印最大元素的堆栈问题）

问题描述

hackerrank 问题陈述是：

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

1 - 将元素 x 推入堆栈。

2 - 删除存在于堆栈顶部的元素。

3 - 打印堆栈中的最大元素。

输入格式

输入的第一行包含一个整数。

接下来的每一行都包含一个上面提到的查询。（保证每个查询都是有效的。）

约束：

输出格式

对于每个类型查询，在新行上打印堆栈中的最大元素。

样本输入

10 1 97 2 1 20 2 1 26 1 20 2 3 1 91 3

样本输出

26 91

我的代码：

n=int(input())
class Stack:
    def __init__(self):
        self.stack1=[]
    def push(self,x):
        return self.stack1.append(x)
    def pop(self):
        self.stack1.pop()
        return
    def maximum(self):
        return max(self.stack1)
stack_object=Stack()
for _ in range(n):
    a=list(map(int,input().split()))
    if a[0]==1:
        stack_object.push(a[1])
    elif a[0]==2:
        stack_object.pop()
    else:
        print(stack_object.maximum())

使用这种时间复杂度 O(n^2) 的算法，我能够通过 27 个测试用例中的 16 个。

有人可以分享一个更优化的时间复杂度 O(n) 的问题的解决方案。

提前致谢。

标签： python-3.xalgorithmoopdata-structuresstack

解决方案

有一个简单的 O(n) 算法。

与其压栈x顶，不如简单地压栈max(x, current_top)。

然后，堆栈的顶部将包含迄今为止推送的所有值的最大值。

推荐阅读