155. Min Stack

https://leetcode.com/problems/min-stack/description/

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.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Thoughts

让stack支持实时返回当前栈内最小元素。让m记录当前最小值，当插入值x比m还小，将m先于x压入s，再把m更新成s。pop时如果栈顶 ==m，再多pop一个并把它的值赋值给m，因为push时上个m值会被先压入s，也就是此时栈顶的下一个元素。

Code

class MinStack:
    
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.s, self.m = collections.deque(), float('inf')
    
    def push(self, x: int) -> None:
        if x <= self.m:
            self.s.append(self.m)
            self.m = x
        self.s.append(x)
        
    def pop(self) -> None:
        if self.s.pop() == self.m:
            self.m = self.s.pop()

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

    def getMin(self) -> int:
        return self.m


# 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()

Analysis

TC: O(N)

Ver. 2

看到了别人的一个stack的解法。本质上是想存下当前min和x，我们何不用一种coding把两个值合并起来。 push时把x - min = top (gap)存入，然后把min单独记下。当pop的值是负数时，更新min为min-pop. peek()时为正数则返回top+min, 否则返回min. 举个例子， [-2, 0, -3] 对应的min是[-2, -2, -3]所以stack是[0, 2, -1], min为-3. 当top()时，peek()=-1, 意味着当前最小min是有当前顶点元素形成的，所以min == top(), 返回-3. 现在pop()，-1抛出，min = -3 - (-1) = -2。这时top()得到的时2，大于0，我们让当前的min + top 还原出x. 依次类推。