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

	def isValid(self, s):
		stack = []
		m = {"(": ")", "{": "}", "[": "]"}
		for char in s:
			if char in m:
				stack.append(char)
			else:
				if len(stack) == 0 or char != m[stack[-1]]:
					return False

				stack.pop()

		return len(stack) == 0

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

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

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

# ()[] OK
# {[()]} OK
# {([]{})} !OK
def isValidString(str):
	stack = []  # space: O(n)
	cur_max_priority = 0
	m = {"(": ")", "{": "}", "[": "]"}
	priority_m = {"{": 1, "[": 2, "(": 3}
	for c in str:  # time: O(n)
		if c in m:  # e.g., {, [, (
			stack.append(c)
			cur_max_priority = max(cur_max_priority, priority_m[c])
			if priority_m[c] < cur_max_priority:  # {([
				return False
		else:  # e.g., ], }, )
			if len(stack) == 0:  # e.g., ]]]]
				return False
			top_element = stack.pop(-1)
			if c != m[top_element]:  # [}
				return False

			if stack:
				cur_max_priority = priority_m[stack[-1]]
			else:  # reset priority
				cur_max_priority = 0

	return len(stack) == 0

	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

	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]

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 = []  # queue1 用于存储栈内的元素
		self.queue2 = []  # queue 作为入栈操作的辅助队列。

	# 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

# Solution 1 - brute force
# - time: O(nums1*nums2)
# - space: O(nums1)
	def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
		m_s1 = {}
		for idx, num in enumerate(nums1):
			m_s1[num] = idx

		res = [-1] * len(nums1)
		for s2_idx in range(len(nums2)):
			if nums2[s2_idx] not in m_s1:
				continue

			for i in range(s2_idx + 1, len(nums2)):
				if nums2[i] > nums2[s2_idx]:
					s1_idx = m_s1[nums2[s2_idx]]
					res[s1_idx] = nums2[i]
					break
		return res


# Solution 2 - use 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][0]:
				idxInNums1 = stack.pop(-1)[1]
				res[idxInNums1] = num
			if num in m:
				idxInNums1 = m[num]
				stack.append([num, idxInNums1])
		return res

# solution 1 - 写法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

# solution 1 - 写法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: List[int]) -> List[int]:
		res = [0] * len(temperatures)
		stack = []  # decreasing monotonic stack, [idx, temperature]
		for idx, temperature in enumerate(temperatures):
			while stack and temperature > stack[-1][1]:
				preIdx, preTemperature = stack.pop(-1)
				res[preIdx] = idx - preIdx
			stack.append([idx, temperature])
		return res