时间戳

首页 > 解决方案 > python中的最大堆栈 - 2堆栈解决方案

python - python中的最大堆栈 - 2堆栈解决方案

问题描述

我正在尝试在 python 中构建一个最大堆栈，我不确定我做错了什么。

这是问题>

设计一个最大栈数据结构，支持栈操作，支持查找栈的最大元素。

实现 MaxStack 类：

  • MaxStack() 初始化堆栈对象。
  • void push(int x) 将元素 x 推入堆栈。
  • int pop() 移除栈顶元素并返回。
  • int top() 获取栈顶元素而不移除它。
  • int peekMax() 检索堆栈中的最大元素而不删除它。
  • int popMax() 检索堆栈中的最大元素并将其删除。
  • 如果最大元素不止一个，则只删除最上面的一个。
class MaxStack:
    def __init__(self):
        self.stack = []
        self.stack_max = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.stack_max or x > self.stack_max[-1][0]:
            self.stack_max.append([x, 1])
        elif x == self.stack_max[-1][0]:
            self.stack_max[-1][1] += 1
        else:
            self.stack_max.append(self.stack_max[-1])

    def pop(self) -> int:
        if not self.stack_max or self.stack:
            return
        if self.stack_max[-1][0] == self.stack[-1]:
            self.stack_max[-1][1] -= 1
        if self.stack_max[-1][1] == 0:
            del self.stack_max[-1]
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

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

    def popMax(self) -> int:
        if self.stack_max:
            return self.stack_max.pop()[0]

示例代码：

obj = MaxStack()
obj.push(6)
param_2 = obj.pop()
param_3 = obj.top()
param_4 = obj.peekMax()
param_5 = obj.popMax()

输入 ：

["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"] [[],[5],[1],[5],[],[],[],[],[],[]]

输出：

[null,null,null,null,5,5,5,5,None,5]

预期的：

[null,null,null,null,5,5,1,5,1,5]

参考： Leetcode 716. 最大栈

标签： python

解决方案

对我来说，跟踪值元组中的计数似乎有点令人困惑，当您可以继续添加到最大堆栈并在需要时从列表中计数它们时。

class MaxStack:

    def __init__(self):
        self.stack = []
        self.maxes = []

    def push(self, n):
        self.stack.append(n)
        if not self.maxes or n >= max(self.maxes):
            self.maxes.append(n)
    
    def pop(self):
        if self.stack:
            val = self.stack.pop()
            if val in self.maxes:
                self.maxes.remove(val)

    def top(self):
        if self.stack:
            return self.stack[-1]
    
    def peek_max(self):
        if self.maxes:
            return self.maxes[-1]
        
    def pop_max(self):
        if self.maxes:
            return self.maxes.pop()

然后，如果您需要每个数量的计数，只需使用 count()：

def max_count(self):
    if self.maxes:
        return self.maxes.count(max(self.maxes))

推荐阅读