[leetcode]155. Min Stack

题目

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

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

分析

建一个栈的数据结构，这个栈很容易的获得栈内元素的最小值。如果用常规的栈结构，最后再通过遍历整个栈获取最小值很耗时。所以，考虑将每一个元素入栈时， 都伴随着它以下元素的最小值一起。比如：

(3,  3) <-- 栈顶
(5,  4)
(4,  4) <-- 栈底

这样在获取最小值时，只需要区栈顶元素即可。

代码

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q = []
        
    def push(self, x: int) -> None:
        self.q.append((x, min(self.getMin(), x)))   

    def pop(self) -> None:
        self.q.pop()    

    def top(self) -> int:
        if not self.q:
            return 
        return self.q[-1][0]

    def getMin(self) -> int:
        if not self.q:
            return float('inf')
        return self.q[-1][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()