Stack

• 支持操作:O(1) Push, O(1) Pop, O(1) Top
• 利用栈暂且保存有效信息

1 Validation系列

stack最经典的用法，保存前面的值方面后面做比较。

20. Valid Parentheses

• 正反括号匹配，想一次做到bug free要细心edge case

# Time : O(n), Space : O(n)
class Solution(object):
    def isValid(self, s):
        stack = []
        chars = {'(':')','[':']','{':'}'}
        for ch in s:
            if ch in "({[":
                stack.append(ch)
            else:
                if not stack or chars[stack.pop()] != ch:
                    return False
        return len(stack) == 0

Design Data Structure

155. Min Stack

设计一个支持O(1)时间找最小值的Stack, 满足getMin(), O(1) get the min number of the stack

• 解法1. Two Stacks
  • One for stacks, One for min Stack!
  • Use Tuple(element, min element) in one Stack

class MinStack(object):

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

    def push(self, x):
        if self.stack:
            self.stack.append((x, min(self.stack[-1][1], x)))
        else:
            self.stack.append((x, x))

    def pop(self):
        self.stack.pop()


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


    def getMin(self):
        if self.stack:
            return self.stack[-1][1]
        else:
            return None

• 解法2. One Stack
  • 如果push的数小于等于min，append两次
  • 个人觉得这种解法和前面解法比起来有些牵强，不过极端情况，比如说递增数组的时候确实可以节省一半的空间。

716. Max Stack

• peekMax() -- Retrieve the maximum element in the stack.
• popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
• 要多设计一个function，每次能删除最顶上的最大值
  • 如果stack保持Array复杂度必然是O(n)
  • 如果要优化肯定会考虑Binary Search Tree

class MaxStack(object):

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

    def push(self, x):
        self.stack.append((x, max(x, self.stack[-1][1] if self.stack else None)))

    def pop(self):
        return self.stack.pop()[0]

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


    def peekMax(self):
        return self.stack[-1][1]

    # Worst Case : O(n)
    def popMax(self):
        m = self.peekMax()
        st = []
        while self.stack[-1][0] != m:
            st.append(self.stack.pop()[0])

        self.stack.pop()
        for n in reversed(st):
            self.push(n)
        return m