python3堆栈_Python3实现最小堆栈

Python3实现最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。

pop() – 删除栈顶的元素。

top() – 获取栈顶元素。

getMin() – 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

解题：

class MinStack:

def __init__(self):

"""

initialize your data structure here.

"""

self.__length = 0

self.__minArr = [] #思路很简单，由于栈先进后出，所以在元素入栈时，把最小值也保存下来，这样不需要每次获取都手动计算最小值了，时间复杂度降至O(1)

self.__arr = []

def push(self, x: int) -> None:

self.__arr.append(x)

self.__minArr.append(x if self.__length == 0 else min(x, self.__minArr[self.__length - 1]))

self.__length += 1

def pop(self) -> None:

self.__arr.pop()

self.__minArr.pop()

self.__length -= 1

def top(self) -> int:

return self.__arr[self.__length - 1]

def getMin(self) -> int:

return self.__minArr[self.__length - 1]

# Your MinStack object will be instantiated and called as such:

# obj = MinStack()

# obj.push(x)

# obj.pop()

# param_3 = obj.top()

# param_4 = obj.getMin()