[25] 用 python 刷 Leetcode: 155 min-stack

原始题目

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

题目分析

设计具有 push, pop, top 操作，并能在常数时间 O(n) 内查询到最小元素的堆叠

解题过程

建立一个 list min_stack纪录堆叠最小值
建立stack list 作为堆叠纪录
push：把值放进堆叠後面，如果该值小於等於 min_stack 堆叠的最後一笔资料，则一并加入 min_stack 堆叠
pop：从 stack 移除最上面一笔值，如果该值等於 min_stack 最後一笔，一并从堆叠移除
top：取得堆叠最上面一个元素stack[-1]
getMin：取得最小值，也就是 min_stack 的最後一个元素min_stack[-1]

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]: 
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()
    
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()