nums = [73, 74, 75, 71, 69, 72, 76, 73]
	stack = []  # (n, idx), mono decreasing stack
	res = [0] * len(nums)  # if there is no clement larger than the current element, the distance is 0
	for idx, num in enumerate(nums):
		while stack and stack[-1][0] < num:
			_, pre_idx = stack.pop()
			res[pre_idx] = idx - pre_idx
			# print(idx, pre_idx)
			# print("while stack", stack)

		stack.append((num, idx))
		# print("not while stack", stack)

	return res

# brute force
#  - time: O(n2)
#  - space: O(n)
    def isValid(self, s: str) -> bool:
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')
        return s == ''
# stack
#  - time: O(n)
#  - space: O(n)
    def isValid(self, s):
        stack = []
        m = {"(": ")", "{": "}", "[": "]"}
        for char in s:
            if char in m:
                stack.append(char)
            else:
                if len(stack) == 0: # )
                    return False
                top = stack.pop()
                if char != m[top]: # [)
                    return False

        return stack # [()

给定一个只包含 "()[]{}" 六种字符的字符串。规定它们的优先级由外至内为："{}", "[]", "()"，同一级的可以嵌套，并列。要求判断给定的字符串是否是合法的括号字串？

例："()", "{((()())())[()]}()" 是合法的。"())", "([])", "())(()", "[{}]" 都是不合法的。
({})

样例1:
[输入]
"{((()())())[()]}()"
[输出]
True

# ()[] OK
# {[()]} OK
# {([]{})} !OK
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        pair_map = {"(": ")", "{": "}", "[": "]"}
        priority_map = {
            "(": 1, ")": 1,
            "[": 2, "]": 2,
            "{": 3, "}": 3
        }
        stack = []  # space: O(n)
        for char in s:  # time: O(n)
            if char in pair_map:
                # 开括号入栈前，若栈顶存在，则要求新开括号优先级 <= 栈顶开括号优先级
                if stack:
                    top_char = stack[-1]
                    if priority_map[char] > priority_map[top_char]:  # 若想要往里嵌套更高优先级的括号，非法
                        return False
                stack.append(char)

            else:
                if len(stack) == 0:  # e.g., ]]]]
                    return False
                top_char = stack.pop()
                if pair_map[top_char] != char:  # [}
                    return False
        return len(stack) == 0

# backtrack + tack
# - time: O(4^N/\sqrt{n})
# - space: O(n)
def generateParenthesis(self, n: int) -> List[str]:
		res = []
		stack = []

		def backTracking(openCountUsed, closeCountUsed):
			if openCountUsed == closeCountUsed == n:  # All open and close have been used
				res.append("".join(stack))
				return

			if openCountUsed < n:  # Still have open to be used
				stack.append("(")
				backTracking(openCountUsed + 1, closeCountUsed)
				stack.pop(-1)

			if closeCountUsed < openCountUsed:  # Able to add a close, e.g., "(()", and not able to add a close if like "()"
				stack.append(")")
				backTracking(openCountUsed, closeCountUsed + 1)
				stack.pop(-1)

		backTracking(0, 0)
		return res

# brute force
# - time: O(n2)
# - space: O(n)
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        while len(tokens) > 1:
            for i in range(len(tokens)):
                if tokens[i] in "+-*/":
                    a = int(tokens[i-2])
                    b = int(tokens[i-1])
                    if tokens[i] == '+':
                        result = a + b
                    elif tokens[i] == '-':
                        result = a - b
                    elif tokens[i] == '*':
                        result = a * b
                    elif tokens[i] == '/':
                        result = int(a / b)
                    tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]
                    break
        return int(tokens[0])
      
# stack
# - time: O(n)
# - space: O(n)
def evalRPN(self, tokens: List[str]) -> int:
		stack = []
		for token in tokens:
			if token == "+":
				res = stack.pop(-1) + stack.pop(-1)
				stack.append(res)
			elif token == "-":
				# e.g., ["13","5","/"] -> 13/5
				n1 = stack.pop(-1)  # 5
				n2 = stack.pop(-1)  # 13
				stack.append(n2 - n1)
			elif token == "*":
				res = stack.pop(-1) * stack.pop(-1)
				stack.append(res)
			elif token == "/":
				n1 = stack.pop(-1)  # 5
				n2 = stack.pop(-1)  # 13
				stack.append(int(n2 / n1))  # The division between two integers always truncates toward zero.
			else:
				stack.append(int(token))
		return stack[-1]

# stack
# - time: O(1)
# - space: O(n)
class MinStack:

	def __init__(self):
		self.stack = []  # [cur_element, cur_min]

	def push(self, val: int) -> None:
		curMin = val
		if len(self.stack) > 0:
			curMin = min(curMin, self.stack[-1][1])
		self.stack.append([val, curMin])

	def pop(self) -> None:
		return self.stack.pop(-1)[0]

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

	def getMin(self) -> int:
		return self.stack[-1][1]

# solution 1 - 两个 queue
class MyStack(object):
	def __init__(self):
		# space: O(n)
		self.queue1 = []  
		self.queue2 = []  

	# time: O(n)
	def push(self, x):
		# 入栈操作时，首先将元素入队到 queue2 ，然后将 queue1 的全部元素依次（从左端）出队并入队到 queue2，此时 queue2的左端的元素即为新入栈的元素，
		# 再将 queue1 和 queue2 互换，则 queue1 的元素即为栈内的元素，queue1 的左端和右端分别对应栈顶和栈底。
		self.queue2.append(x)
		while self.queue1:
			self.queue2.append(self.queue1.pop(0))
		self.queue1, self.queue2 = self.queue2, self.queue1

	# 由于每次入栈操作都确保 queue1 的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。
	# 出栈操作只需要移除 queue1 的前端元素并返回即可，获得栈顶元素操作只需要获得 queue1 的前端元素并返回即可（不移除元素）。
	def pop(self):
		return self.queue1.pop(0)

	def top(self):
		return self.queue1[0]

	def empty(self):
		# 由于 queue1 用于存储栈内的元素，判断栈是否为空时，只需要判断 queue1 是否为空即可。
		return not self.queue1

  
# solution 2 - 一个 queue
class MyStack(object):
	def __init__(self):
		# space: O(n)
		self.queue = []

	# time: O(n)
	def push(self, x):
		n = len(self.queue)
		self.queue.append(x)
		for _ in range(n):
			self.queue.append(self.queue.pop(0))

	def pop(self):
		return self.queue.pop(0)

	def top(self):
		return self.queue[0]

	def empty(self):
		return not self.queue

class MyQueue:
	def __init__(self):
		# space: O(n). 最差情况下，栈 A 和 B 共保存 N 个元素。
		self.inStack = []
		self.outStack = []

	# time: O(1)
	def push(self, x: int) -> None:
		self.inStack.append(x)

	# pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)
	def pop(self) -> int:
		self.peek()
		return self.outStack.pop()

	# pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)
	def peek(self) -> int:
		if not self.outStack:
			while self.inStack:
				self.outStack.append(self.inStack.pop(-1))
		return self.outStack[-1]

	# time: O(1)
	def empty(self) -> bool:
		return not self.inStack and not self.outStack

# brute force
# - time: O(nums1*nums2)
# - space: O(nums1)
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        m = {}
        for i, num in enumerate(nums1):
            m[num] = i

        res = [-1] * len(nums1)
        for i, num in enumerate(nums2):
            if num not in m:
                continue

            for j in range(i + 1, len(nums2)):
                if nums2[j] > num:
                    index = m[num]
                    res[index] = nums2[j]
                    break

        return res

# use monotonic stack
# - time: O(nums1) + O(nums2)
# - space: O(nums1)
	def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
		m = {}  # space: O(nums1)
		for idx in range(len(nums1)):  # time: S(s1)
			m[nums1[idx]] = idx

		stack = []  # space: O(nums1)
		res = [-1] * len(nums1)
		for num in nums2:  # time: O(s2)
			while stack and num > stack[-1]:
				idxInNums1 = stack.pop(-1)
				res[idxInNums1] = num
			if num in m: # if num not in m, doesn't need to care about num (since num doesn't affect res)
				idxInNums1 = m[num]
				stack.append(num)
		return res

# monotonic stack - 写法1
# - time: O(n)
# - space: O(n)
	def nextGreaterElements(self, nums: List[int]) -> List[int]:
		res = [-1] * len(nums)
		stack = []  # decreasing monotonic stack, [val, idx]
		for idx, num in enumerate(nums):
			while stack and num > nums[stack[-1]]:
				preIdx = stack.pop(-1)
				res[preIdx] = num
			stack.append(idx)

		# 只遍历一次序列是不够的，例如序列 [2,3,1]，最后单调栈中将剩余 [3,1][，其中元素 [1] 的下一个更大元素还是不知道的。
		for idx, num in enumerate(nums):
			while stack and num > nums[stack[-1]]:
				preIdx = stack.pop(-1)
				res[preIdx] = num
		# stack.append([num, idx]) # for the second loop, don't need to call this function, but no harm to do so

		return res

# monotonic stack - 写法2
# - time: O(n)
# - space: O(n)
	def nextGreaterElements(self, nums: List[int]) -> List[int]:
		res = [-1] * len(nums)
		stack = []  # decreasing monotonic stack, [val, idx]
		# 只遍历一次序列是不够的，例如序列 [2,3,1]，最后单调栈中将剩余 [3,1][，其中元素 [1] 的下一个更大元素还是不知道的。
		for _ in range(2):
			for idx, num in enumerate(nums):
				while stack and num > nums[stack[-1]]:
					preIdx = stack.pop(-1)
					res[preIdx] = num
				stack.append(idx)

		return res

# decreasing monotonic stack 
# - time: O(n)
# - space: O(n)
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        stack = []  # decreasing monotonic stack
        res = [0] * len(temperatures)
        for idx in range(len(temperatures)):
            temperature = temperatures[idx]
            while stack and temperature > temperatures[stack[-1]]:
                preIdx = stack.pop(-1)
                res[preIdx] = idx - preIdx
            stack.append(idx)
        return res