主页 / 问题 / 1286182
Accepted
bdc1
Asked:2022-05-26 05:20:05 +0000 UTC2022-05-26 05:20:05 +0000 UTC

堆栈 - python中的任务

  • 772

我完全不明白如何解决这个问题，我要求对代码进行更多解释。

实现一个类，该类StackMaxEffective支持确定堆栈上元素之间的最大值的操作。操作的复杂度应该是 O(1)。对于空堆栈，操作必须返回None。在这种情况下push(x)， 和pop()也必须在恒定时间内执行。

输入格式

第一行包含一个数字——命令的数量，它不超过 100000。然后是命令，每行一个。命令可以是以下类型：

  • push(x)— 将数字 x 添加到堆栈中；
  • pop()- 从栈顶移除一个数字；
  • get_max()- 打印堆栈上的最大数量；

如果堆栈为空，则在调用命令时，需要为命令get_max打印- 。«None»pop«error»

输出格式

对于每个命令get_max()，打印其执行结果。如果堆栈为空，对于命令get_max()，键入«None»。如果从空堆栈中删除，请打印«error»。

示例 1：

输入：

10
pop
pop
push 4
push -5
push 7
pop
pop
get_max
pop
get_max

结论：

error
error
4
None

示例 2：

输入：

10
get_max
push -6
pop
pop
get_max
push 2
get_max
pop
push -2
push -6

结论：

None
error
None
2

Python 3.7.3 | 时间限制 - 1.5 秒 | 内存限制 - 64Mb

我的代码：

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

    def push(self, item):

        if bool(self.items) and bool(self.max_items):
            if item >= self.max_items[-1]:
                self.max_items.append(item)
            return self.items.append(item)
        self.items.append(item)
        self.max_items.append(item)

    def pop(self):
        if bool(self.items) and bool(self.max_items):
            if self.items[-1] == self.max_items[-1]:
                self.max_items.pop()
            return self.items.pop()
        return 'error'

    def get_max(self):
        if bool(self.items) and bool(self.max_items):
            return self.max_items[-1]
        return None
python

1 个回答

  1. Best Answer

    让我先给你一个想法。制作一个同时存储值和最大值的堆栈。例如：

    команда  стек                          результат
pop      []                            error
pop      []                            error
push 4   [(4, 4)]
push -5  [(4, 4), (-5, 4)]
push 7   [(4, 4), (-5, 4), (7, 7)]
pop      [(4, 4), (-5, 4)]
pop      [(4, 4)]
get_max  [(4, 4)]                      4
pop      []
get_max  []                            None

    猜猜如何记录和使用最大值。

    PS 仔细看条件，可以理解为没有使用pair的第一个值。也就是说，您只需要将最大值存储在堆栈中。像这样：

    команда  стек         результат
pop      []           error
pop      []           error
push 4   [4]
push -5  [4, 4]
push 7   [4, 4, 7]
pop      [4, 4]
pop      [4]
get_max  [4]          4
pop      []
get_max  []           None

    在这个特定的实现中，堆栈是多余的：它存储了值和最大值。但它有一个正常的界面：

    class StackMaxEffective:
    def __init__(self):
        self.stack_ = []

    def __bool__(self):
        return bool(self.stack_)

    def push(self, item):
        if self.stack_:
            new_max = max(item, self.stack_[-1][1])
        else:
            new_max = item
        self.stack_.append((item, new_max))

    def pop(self):
        return self.stack_.pop()[0]

    def get_max(self):
        return self.stack_[-1][1]


s = StackMaxEffective()
for _ in range(int(input())):
    cmd = input().split()
    if cmd[0] == 'pop':
        if s:
            s.pop()
        else:
            print('error')
    if cmd[0] == 'push':
        s.push(int(cmd[1]))
    if cmd[0] == 'get_max':
        if s:
            print(s.get_max())
        else:
            print('None')
    • 5

相关问题