使用单调栈的场景：
- 如果要求返回的结果，或者结果是与数组中数的大小值有关系，需要使用单调栈（递增，或递减）
- 对于消除的问题，需要使用栈
- 最大矩形面积，柱子组成的面积，找到左右两端第一个比当前高度，面积小的数
1190，反转每对括号间的子串，中等
核心方法：使用栈，只要不是遍历到右括号，就入栈；遇到右括号，则反转内层字符串，然后再加入栈顶
难点：注意内层字符串反转完成后，需要弹出栈顶元素，因为此时的栈顶元素为左括号
复杂度分析：
- 时间复杂度：O(n) n为字符串的长度
- 空间复杂度：O(k) k为字符串的长度
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = []
for c in s:
if c != ')':
stack.append(c)
else:
tmp = []
while stack and stack[-1] != '(':
tmp.append(stack.pop())
stack.pop() # 弹出栈顶元素
stack += tmp
return ''.join(stack)224，基本计算器，困难
核心方法：栈。当括号展开后，如果原括号前面是负号，那么原括号内的数字都要进行符号反转。栈中存放的是从当前位置向前算，所有符号的综合影响的结果。遍历到哪个位置，如果这个位置是+号，那么就直接取出最近的符号；如果这个位置是-减号，那么就直接取出最近的符号的负号；如果这个位置是左括号，那么将最近符号压入栈中；如果是右括号，则弹出栈顶符号。
难点：这里栈的作用就是记录括号前的符号！遍历到哪里，就计算到哪里。注意，可能存在字符串转化为数字后大于9的情况，此时要上一个结果*10。每遇到一个左括号，向栈中压入这个左括号前的符号；每遇到一个右括号，从栈中弹出一个符号
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def calculate(self, s: str) -> int:
ops = [1] # 初始化栈，栈里只存放符号
sign = 1 # 初始化符号为1，默认为+号
ret = 0 # 结果
n = len(s)
i = 0
while i < n:
if s[i] == ' ': # 遇到空格，跳过
i += 1
elif s[i] == '+': # 遇到+号时，取出栈顶符号
sign = ops[-1]
i += 1
elif s[i] == '-': # 遇到-号时，取出栈顶符号的负值
sign = -ops[-1]
i += 1
elif s[i] == '(': # 遇到左括号，向栈中压入当前符号
ops.append(sign)
i += 1
elif s[i] == ')': # 遇到右括号，弹出一个符号，说明此时括号内的计算完毕，括号前的那个符号就不要了
ops.pop()
i += 1
else: # 遇到数字的情况
num = 0
while i < n and s[i].isdigit():
num = num * 10 + ord(s[i]) - ord('0') # 累加得到同一个数
i += 1
ret += num * sign # 将当前和添加进结果中，实际的加减运算是在这里完成的
return ret1047，删除字符串中的所有相邻重复项，简单
核心方法：栈。栈不为空且栈顶元素等于当前元素时，栈弹出一个元素；否则将当前元素入栈。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def removeDuplicates(self, S: str) -> str:
stack = list()
for ch in S:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)
return ''.join(stack)剑指offer09，用两个栈实现队列，简单
核心方法：两个栈，栈1用来添加，栈2用来删除。对于在队尾添加的情况，直接添加进栈1；对于队头删除的情况，首先判断栈2是否不为空，如果不为空则直接出栈；如果为空，判断栈1是否为空，如果为空，则返回-1；如果栈1不为空，将栈1中的数依次出栈添加进栈2，然后栈2出栈一个数
复杂度分析：
- 时间复杂度：添加O(1)，删除可能导致栈1中元素全部出栈，复杂度为O(n)
- 空间复杂度：O(n)，最差情况下，两个栈各保存n各元素
class CQueue:
def __init__(self):
self.A, self.B = [], []
def appendTail(self, value: int) -> None:
self.A.append(value)
def deleteHead(self) -> int:
if self.B:
return self.B.pop()
elif not self.A:
return -1
else:
while self.A:
self.B.append(self.A.pop())
return self.B.pop()103，二叉树的锯齿形层序遍历，中等
核心方法：广度优先搜索，队列，双端队列
难点：每次将当前节点的左右子节点存入队列。当这个队列不为空时，根据当前队列个数，新建双端队列，通过树的层级奇偶形确定当前节点的值是添加在双端队列的头部还是尾部。对队列中每个元素处理时，双端队列的结果都要转化为列表，添加进结果中
注意：双端队列用来存储每行的遍历结果（正序或者倒叙）；普通队列用来按行顺序从左到右存储每行的节点
时间复杂度：O(n) 每个节点都会被遍历一次
空间复杂度：两个队列需要维护，O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return [] # 特殊情况处理
# 初始化 queue 队列先存入根节点
queue = deque()
queue.append(root)
# 用来标记当前层是偶数层还是奇数层
is_even_level = True
# 结果列表
ans = []
# 队列不为空时，开始进行遍历
while queue:
# 声明双端队列 level_queue
level_queue = deque()
# 先计算 queue 的长度 size
size = len(queue)
# 取出 size 个元素
for _ in range(size):
# 取出节点
node = queue.popleft()
# 偶数层，将节点值插入到 level_queue 尾部
if is_even_level:
level_queue.append(node.val)
# 奇数层，将节点值插入到 level_queue 头部
else:
level_queue.appendleft(node.val)
# 将下一层的节点存放到 queue 中
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 这里注意，将双端队列转换为列表的形式，存入结果列表中
ans.append(list(level_queue))
# 维护更新 is_even_level
is_even_level = not is_even_level
return ans394，字符串解码，中等
核心方法：使用栈。
难点：创建临时结果res和乘积变量multi，分别记录拆开括号后（即重复k次后）的结果和[前的乘数
时间复杂度：O(n)
空间复杂度：极端情况需要线性空间 O(n)
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
# 当遇到前括号时，将括号前的乘数和临时结果入栈
stack.append([multi, res])
res, multi = "", 0 # 重制乘数和临时结果
elif c == ']':
# 当遇到后括号时，出栈，记录乘数和上一次临时结果
cur_multi, last_res = stack.pop()
# 当前字符串重复并与上一个临时结果进行拼接
res = last_res + cur_multi * res
elif '0' <= c <= '9':
# 等于数字时需要整理乘数，乘10是为了保证multi不止个位
multi = multi * 10 + int(c)
else:
# 同一括号内的字母要进行拼接
res += c
return res402，移动K位数字，中等
核心方法：贪心，单调栈，两个数比较，最左边数字的大小决定了这两个数的大小
难点：给顶一个长度为n的数字序列，从左往右找到第一个位置使得这个位置的值小于前一个位置的值，并删去前一个位置的值；如果不存在则说明整个序列单调不降，删除最后一个数即可。类似的，可以使用一个栈维护当前答案序列。栈中的元素代表截止到当前位置，删除不超过 k 个数字后，所能得到的最小整数。栈中维护的是一个单调递增的数字序列
复杂度分析：
- 时间复杂度：O(n)，主循环的时间复杂度被限制在2n以内
- 空间复杂度：O(n)
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
numStack = []
# 构建单调递增的数字串
for digit in num:
while k and numStack and numStack[-1] > digit:
# 当k不为0，且栈不为空，且栈顶元素大于当前数时就弹出
numStack.pop()
k -= 1
# 当前元素入栈
numStack.append(digit)
# 如果 K > 0，删除末尾的 K 个字符，因为栈是单调递增的，末尾数大，所以要从末尾开始删除
finalStack = numStack[:-k] if k else numStack
# 抹去前导零
return "".join(finalStack).lstrip('0') or "0"456，132模式，中等
核心方法：单调栈；枚举2
难点：
-
132 的数字顺序表示的是其模式索引排序，数字大小表示的模式中真实数字大小
-
单调栈中存放的是所有可以作为
2(k)的元素，并且是单调递减的； -
使用
max_k维护所有可以作为2的元素的最大值； -
数组的遍历方式为从右到左进行遍历，这样产生的
1(i)和3(j)的范围更大； -
【判断1】每次遍历中，首先判断当前元素是否能够作为1，即1元素小于2元素（此时的2元素由
max_k表示），如果满足，则返回True；由于一开始设置了max_k为无限小，所以这里并不会一开始就满足条件，一定是满足已经遍历过的元素3(j)大于2(k)的基础上才会发生的； -
【判断2】然后判断当前元素是否能够作为3，即需要保证遍历的元素要大于当前栈顶元素，如果这个条件不满足，且当前元素大于
max_k，则将当前元素进栈；如果这个条件满足，那么更新max_k直到条件不满足，那么此时找到的max_k就是当前元素3对应的最大的元素2； -
此时如果【判断1】满足，说明找到了；否则就是没有找到
总结 ：遍历数组时，上一轮遍历到的元素为3，当前轮遍历到的元素为1，在元素3大于元素2的条件下更新元素2的最大值，当前元素1大于当前元素2的最大值时，当前元素1进行压栈
复杂度分析：
- 时间复杂度：O(n)，且每一个元素最多被加入和弹出单调栈各一次，因此操作单调栈也为 O(n)
- 空间复杂度：O(n)，即为单调栈需要使用的空间。
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
n = len(nums)
candidate_k = [nums[n - 1]]
max_k = float("-inf")
for i in range(n - 2, -1, -1):
# 判断1
if nums[i] < max_k:
# 此时的nums[i]为元素1
return True
# 判断2
while candidate_k and nums[i] > candidate_k[-1]:
# 此时的nums[i]为元素3
max_k = candidate_k[-1]
candidate_k.pop()
if nums[i] > max_k:
candidate_k.append(nums[i])
return False227，基本计算器2，中等
核心方法：使用栈；因为乘除法具有优先顺序，所以首先计算乘除法；
难点：
- 维护一个
preSign用来保存前一个计算符，num为最近产生的数 - 遇到数字的话处理方式比较固定；
- 如果遇到加号，则当前元素直接入栈；
- 遇到减号，当前元素取相反数后入栈；
- 遇到乘法（除法），将
num与栈顶元素进行计算，符号为乘法（除法），其实计算的都是上一个记录的preSign和num - 注意：如果遇到符号，处理结束后要更新
preSign和num - 最后进行栈中的数求和
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def calculate(self, s: str) -> int:
stack = [] # 栈中存放数字
n = len(s)
preSign = '+' # 记录前一个符号
num = 0
for i in range(n):
if s[i] != ' ' and s[i].isdigit():
num = num * 10 + ord(s[i]) - ord('0')
if i == n-1 or s[i] in '+-*/':
# i==n-1表示遍历到最后一个，别忘记数据进栈
if preSign == '+':
stack.append(num)
elif preSign == '-':
stack.append(-num)
elif preSign == '*':
stack.append(stack.pop() * num) # 使用的是前一个 num
else:
stack.append(int(stack.pop() / num))
preSign = s[i]
num = 0
return sum(stack)316，去除重复字母，中等
核心方法：
难点：字典序最小的意思是，尽量按照26个英文字母顺序进行排序。使用栈。
- 首先统计
s中每个字符出现的频率，使用字典，key为字符，value为频率，表示每个字符的剩余出现次数；这个字典的作用是用来判断存入栈中的字符是否还有剩余，如果还有剩余，那么在遇到比栈顶元素小的字符时，就可以进行替换（将来还有可能重新入栈）以满足最小字典序的要求；否则不能替换，因为替换后不满足每个字符至少出现出现一次的要求 - 每次遍历到的字符，在字典中对应字符的剩余出现次数减1
- 当同时满足栈不为空，当前遍历元素小于栈顶元素，且栈顶元素的剩余个数大于0时，可以出栈
- 每个不在栈中的元素，都应该入栈
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def removeDuplicateLetters(self, s) -> int:
stack = []
# 统计每个字符出现的频率
remain_counter = collections.Counter(s)
for c in s:
if c not in stack:
while stack and c < stack[-1] and remain_counter[stack[-1]] > 0:
stack.pop()
stack.append(c)
remain_counter[c] -= 1
return ''.join(stack)341，扁平化嵌套列表迭代器，中等
核心方法一：递归。提前一次性将所有嵌套列表全部展开，但是不推荐这种方法
时间复杂度：O(n) dfs
空间复杂度：O(n)
class NestedIterator(object):
def dfs(self, nests):
# 递归开始，每次判断是否是整数，如果是整数就将整数添加进队列中
# 如果是列表，就将这个列表作为要拆开的对象进行递归
for nest in nests:
if nest.isInteger():
self.queue.append(nest.getInteger())
else:
self.dfs(nest.getList())
def __init__(self, nestedList):
self.queue = collections.deque()
self.dfs(nestedList) # 开始递归
def next(self):
return self.queue.popleft() # 直接pop出队列的头
def hasNext(self):
return len(self.queue) # 通过判断队列的长度是否为0来确定是否队列还有元素核心方法二：迭代，使用栈，在调用next和hasNext时扁平化当前嵌套的子列表，也就是一边迭代，一边获取当前结果
- 在遍历时逆序将所有元素放入栈，不管其是int还是list（不必展开）
- 在
hasNext()中判断栈顶元素是否为int- 如果是，返回
True，然后会调用next取出这个int - 如果是
list，则需要将这个list中所有数逆序压栈 - 栈为空，嵌套列表已结束，返回false
- 如果是，返回
- 复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class NestedIterator(object):
def __init__(self, nestedList):
self.stack = []
# 将原始输入逆序压栈
for i in range(len(nestedList) - 1, -1, -1):
self.stack.append(nestedList[i])
def next(self):
# 弹出栈顶元素，并获取其int值
cur = self.stack.pop()
return cur.getInteger()
def hasNext(self):
while self.stack:
# 栈不为空的情况下，先取出栈顶元素，判断其是否为int
cur = self.stack[-1]
if cur.isInteger():
return True
# 如果栈顶元素不是int，先出栈，然后将其展开后逆序添加进栈
self.stack.pop()
for i in range(len(cur.getList()) - 1, -1, -1):
self.stack.append(cur.getList()[i])
return False145，二叉树的后续遍历，中等
核心方法一：直接递归。后续遍历，先遍历左子树，然后遍历右子树，最后遍历自己
时间复杂度：O(n)
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def postorder(node):
if not root: return
postorder(node.left)
postorder(node.right)
res.append(root.val)
res = []
postorder(root)
return res核心方法二：迭代，递归其实是隐式的维护了一个栈，而迭代是显示维护栈，具体思路见代码
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return list()
res = list()
stack = list()
prev = None # prev指针指向上一个节点
while root or stack:
# 如果当前节点和栈有一个不为空
while root:
# 一直从头寻找左子树，直到左子树为空
stack.append(root)
root = root.left
# 弹出最新的节点
root = stack.pop()
if not root.right or root.right == prev:
# 如果右子树为空，或右子树等于前一个节点
res.append(root.val)
prev = root
root = None
else:
# 如果右子树不为空，则将root重新入栈，并更新root为当前节点的右子树
stack.append(root)
root = root.right
return res84，柱状图中的最大矩形，困难
核心方法一：单调栈：
难点：
-
栈的作用：针对一个元素，查到向两边遍历的过程中最近的高度小于当前元素的高度的那个元素对应的索引，也就是说栈的设置是为了将每个元素两个边界对应的索引位置进行标记，数值赋值结果列表中后就没用了。
-
大于当前元素高度要出栈的原因：如果有两根柱子
$j_0$ 和$j_1$ ，其中$j_0$ 在$j_1$ 的左侧，并且$j_0$ 的高度大于$j_1$ ，那么在后面的柱子$i$ 向左找小于其高度的柱子时，$j_1$ 会挡住$j_0$ ，那么高度小于当前元素（每次遍历时）的元素索引就可以直接出栈了。 -
从左向右遍历，记录索引位置时，如果栈已经为空了，说明前面没有小于当前元素的元素，则这个位置的索引值设置为-1；同理，从右向左遍历，记录索引位置时，如果栈已经为空了，说明后面没有小于当前元素的元素，则这个位置的索引值设定为n，即数组长度
-
复杂度分析
- 时间：O(n)
- 空间：O(n)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
if n < 1: return 0
left, right = [0] * n, [0] * n
# 从左向右遍历，能够找到每个元素左边最近的高度小于当前元素高度的元素索引
# 求出了每根柱子的左边界
idx_stack = list() # 栈中存入的是元素的下标
for i in range(n):
while idx_stack and heights[idx_stack[-1]] >= heights[i]:
idx_stack.pop()
left[i] = idx_stack[-1] if idx_stack else -1
idx_stack.append(i)
# 从右向左遍历，能够找到每个元素右边最近的高度小于当前元素高度的元素索引
# 求出了每根柱子的右边界
idx_stack = list()
for i in range(n-1, -1, -1):
while idx_stack and heights[idx_stack[-1]] >= heights[i]:
idx_stack.pop()
right[i] = idx_stack[-1] if idx_stack else n
idx_stack.append(i)
# 对应位置取左右边界，即面积的最大值
ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n))
return ans核心方法二（推荐）：
- 难点：
- 当一个元素索引被弹出栈时，也能够找到这个元素的右边界；因为弹出条件时，栈顶元素要大于当前遍历到的元素，说明这两个元素之间没有小于栈顶元素的情况。于是在出栈时就记录这个右边界
- 在遍历结束后，栈中仍然有一些位置，这些位置对应的右边界就是位置为 n 的「哨兵」。我们可以将它们依次出栈并更新右边界，也可以在初始化右边界数组时就将所有的元素的值置为 n。
- 复杂度分析
- 时间：O(n)
- 空间：O(n)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
if n < 1: return 0
# 初始化右边界时，直接将各个位置初始化为n
left, right = [0] * n, [n] * n
idx_stack = list()
for i in range(n):
while idx_stack and heights[idx_stack[-1]] >= heights[i]:
# 记录每个位置的右边界
right[idx_stack[-1]] = i
idx_stack.pop()
left[i] = idx_stack[-1] if idx_stack else -1
idx_stack.append(i)
ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n))
return ans
150，逆波兰表达式求值，中等
核心方法：使用栈
难点：逆波兰表达式的特点是，计算符在两个待计算的数后面，即使去掉了括号，依旧可以根据顺序进行计算；如果遇到数字就压栈，如果遇到计算符，就依次弹出栈顶的两个元素，先弹出来的在算符右边，后弹出来的在算符左边，不要忘记计算完成后需要重新压栈。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
opt_dict = {'+': add,
'-': sub,
'*': mul,
'/': lambda x,y: int(x/y)}
stack = list()
for token in tokens:
try:
num = int(token)
except Exception as e:
nums1 = stack.pop()
nums2 = stack.pop()
num = opt_dict[token](nums2, nums1)
finally:
stack.append(num)
return stack[0]核心方法二：使用一个数组模拟栈，预先定义好数组的长度，通过操作数组中的索引来给数据进行赋值
- 时间复杂度：O(n)，其中 n 是数组 tokens 的长度。
- 空间复杂度：O(n)，其中 n 是数组 tokens 的长度。需要创建长度为
$\frac{n+1}{2} $
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
opt_dict = {"+": add,
"-": sub,
"*": mul,
"/": lambda x, y: int(x / y)}
# 需要注意 python 中负数除法的表现与题目不一致
n = len(tokens)
# 数组的最大长度是固定的，数字总比计算符多一个，所以最大长度为(n + 1) // 2
stack = [0] * ((n + 1) // 2)
index = -1 # index的初始化为-1
for token in tokens:
try:
# 如果数字进入数组，那么索引要加1
num = int(token)
index += 1
stack[index] = num
except ValueError:
# 如果遇到运算符，对数组中两个数运算后还会添加进一个，总的来说数组中会少一个数
index -= 1
# 实际计算的是当前数和前一个数
stack[index] = opt_dict[token](stack[index], stack[index + 1])
return stack[0]23，用栈实现队列，简单
核心方法：两个栈，一个作为输入栈，一个作为输出栈。push时，将元素压入输入栈；pop/peek时，则从输出栈弹出；如果输出栈为空，那么将输入栈依次弹出压入输出栈。
- 时间复杂度：
push()时间复杂度是 O(1)；peek()/pop()均摊时间复杂度是 O(1)，单步操作的最坏时间复杂度是 O(N)。 - 空间复杂度：空间复杂度是 O(N)
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack1 = list()
self.stack2 = list()
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack1.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty. 两个栈都为空才返回True
"""
return not self.stack1 and not self.stack2
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()199，二叉树的右视图，中等
核心方法一 推荐：使用栈，深度优先搜索。在每一次搜索过程中，总是先访问右子树。对于每一层来说，我们在这层见到的第一个节点一定是最右边的节点（因为使用了栈）
难点：广度优先体现在每次从栈中pop出的都是每一层最右边节点。因为每次从栈pop出来的首先是右子树，所以只要这个右子树不为空，那么就会在字典中留下深度键对应的节点值，之后即使在同一层下有的节点也不为空，字典中深度键对应的节点值也是不会改变的；总之，字典的setdefault方法和栈共同保证了右视图。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
rightmost_value_at_depth = dict() # 键：深度，值：节点的值
stack = [(root, 0)]
while stack:
node, depth = stack.pop()
if node is not None:
# 如果不存在对应深度的节点我们才插入
# 也就是说，如果depth不存在了，会添加键depth并将值设置为node.val
# 只有遍历到下一层的情况下，字典才会更新（添加新的键值对）
# 每一层存在的最右边节点决定了字典的更新，而栈决定了输出的节点一定是最右的
rightmost_value_at_depth.setdefault(depth, node.val)
stack.append((node.left, depth + 1))
stack.append((node.right, depth + 1))
return list(rightmost_value_at_depth.values())核心方法二：使用队列，广度优先搜索
难点：深度优先体现在每次从队列中pop出来的，都是每层从左往右遍历的节点，所以需要不断更新字典（也就是每一个深度对应的节点值），直到遍历到下一层。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
queue = deque([(root, 0)])
while queue:
node, depth = queue.popleft()
if node is not None:
# 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
rightmost_value_at_depth[depth] = node.val
queue.append((node.left, depth + 1))
queue.append((node.right, depth + 1))
return list(rightmost_value_at_depth.values())239，滑动窗口最大值，困难
核心方法：双端队列记录当前滑动窗口的元素索引，队列最左端记录最大元素的索引。
- 当遍历到的元素已经超过当前窗口内数据时，上一个最大就不适用了，需要双端队列左弹出
- 然后弹出队尾索引对应元素小于当前遍历元素的索引，以此来保证最左侧元素为最大
- 每次产生的最大数都是从双端队列的第一个数
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：
- 双端队列：O(k)，
- 返回结果：O(n-k+1)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
queue = collections.deque()
for i, num in enumerate(nums):
# 遍历其实是在模拟窗口的变化
if queue and queue[0] == i - k:
# 表示当前遍历到的i已经超过了上一个k窗口内的数，
# 上一个k窗口中的最大值已经不满足了，所以要将这个最大值弹出
queue.popleft()
while queue and nums[queue[-1]] < num:
# 循环来保证双端队列最左侧元素值最大
queue.pop()
queue.append(i)
if i >= k - 1:
# i >= k-1 表示此时i已经遍历了k个数了，可以取k个数中的最大值了
res.append(nums[queue[0]])
return res907，子数组的最小值之和，中等
核心方法：使用单调栈，确定arr[i]为子数组的最小值时，这个子数组的左右边界left和right（这里的left和right都是小于arr[i]的）。此时arr[i]就是最长子数组arr[left+1: right]的最小值。那么以arr[i]为最小值的子数组的个数就为 (i - left[i]) * (right[i] - i)。
难点：
-
单调栈是一个单调递增栈，里面存放的是当前元素的左边界（当前元素向左进行遍历时，遇到的第一个小于它的数）。
-
如果向左进行遍历时，前面的元素比当前元素要大，则直接出栈
-
如果栈不为空，那么栈顶元素就是离当前元素最近的小于它的数，也就是左边界
-
同样的操作，针对右边界再从后向前遍历一遍，总共两次遍历
-
在比较栈顶元素和当前元素时，需要保证
left或right有一端要取小于等于。这样做的原因是假设了每个子数组如果最小值多次出现，那么只取第一次出现的最小值。这样，例如[1,1,1]这样结构的情况，也可以取出6种数组以1为最小值 -
时间复杂度O(N)
-
空间复杂度O(N)
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n = len(arr)
if n == 0: return 0
if n == 1: return arr[0]
ans = 0
# 将初始值全部置为0
left, right = [0] * n, [0] * n
stack = list()
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
if not stack:
left[i] = -1
else:
left[i] = stack[-1]
stack.append(i)
stack = list()
for i in range(n-1, -1, -1):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
if not stack:
right[i] = n
else:
right[i] = stack[-1]
stack.append(i)
for i in range(n):
ans += (i- left[i]) * (right[i] - i) * arr[i]
ans %= 1000000007
return ans核心方法：还是使用单调栈，通过一次遍历完成。
难点：将原始数组的左右两端分别加入无穷小：float('-inf')。维护一个单调递增栈，只要遍历时遇到一个字符是小于当前栈顶元素的，那么新的栈顶元素与当前遍历到的元素就成为弹出元素的左右边界。原来的(i- left[i]) * (right[i] - i) * arr[i]就变为了(cur - stack[-1]) * (i - cur) * arr[cur]
-
时间复杂度O(N)
-
空间复杂度O(N)
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n = len(arr)
ans = 0
arr = [float('-inf')] + arr + [float('-inf')]
stack = list()
for i, a in enumerate(arr):
while stack and arr[stack[-1]] > a:
cur = stack.pop()
ans += (cur- stack[-1]) * (i - cur) * arr[cur]
stack.append(i)
return ans % (10**9+7)1106，解析布尔表达式，困难
核心方法：双栈，一个存放运算法，一个存放非右括号，非运算符的字符
- 时间复杂度：O(len(expression))
- 空间复杂度：最坏情况下 O(len(expression))
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
# 双栈，stack_op 用来记录操作符，stack_ch 用来操作非右括号的字符
stack_op, stack_ch = list(), list()
for i in expression:
ops = set(['|', '&', '!'])
if i in ops:
# 如果遇到运算符，则加入运算符栈
stack_op.append(i)
elif i == ')':
# 如果遇到右括号，则表示可以计算
bools = list()
while stack_ch[-1] != '(':
# 将字符栈中所有的t或f全部取出，直到遇到左括号
if stack_ch[-1] == 't':
bools.append(True)
elif stack_ch[-1] == 'f':
bools.append(False)
stack_ch.pop()
# 将左括号弹出
stack_ch.pop()
# 将对应运算符弹出
op = stack_op.pop()
# 计算结果，并将计算好的结果再入栈
if op == '!':
stack_ch.append('t' if not bools[-1] else 'f')
elif op == '|':
stack_ch.append('t' if any(bools) else 'f')
elif op == '&':
stack_ch.append('t' if all(bools) else 'f')
else:
# 非右括号的全部入栈
stack_ch.append(i)
return True if stack_ch[0] == 't' else False726，原子的数量，困难
核心方法：使用栈，用来存放每组数据Counter对象（每个括号为一组，括号之外的算作一组）
-
遍历字符串时，遍历到的字符主要分成3种情况
- 遇到左括号，则需要向栈中加入新的Counter对象，等待括号内的元素加入
- 遇到右括号，则弹出（展开）栈顶的Counter对象，处理括号外的元素数量，与括号内的元素数量相乘后，将新的数量添加到上一个Counter对象中
- 遇到大写字母，就是化学元素的头，首先需要确定化学元素的长度，即名称；然后确定这个化学元素的个数，将新的数量添加到上一个Counter对象中
-
注意：
- 最后返回的化学元素排序结果是按照字母表的顺序来的
- 要求元素数量为1的在结果中不显示数量，最后返回时，元素的个数等于1的，拼接的个数为空
时间复杂度：$O(n^2)$
时间复杂度：$O(n)$
class Solution(object):
def countOfAtoms(self, formula):
N = len(formula)
# 栈用来存放每组数据Counter对象
stack = [collections.Counter()]
i = 0
while i < N:
if formula[i] == '(':
# 遇到左括号，向栈中加入新Counter对象，括号内的元素和数量会被加入到counter中
stack.append(collections.Counter())
i += 1
elif formula[i] == ')':
# 弹出栈顶counter
top = stack.pop()
# 获取括号外的元素数量
i += 1
i_start = i
while i < N and formula[i].isdigit(): i += 1
multiplicity = int(formula[i_start: i] or 1)
for name, v in top.items():
# 展开括号后，外部的数量乘以内部的数量，再加上栈顶counter中该元素原本数量
stack[-1][name] += v * multiplicity
else:
# 找到一个化学元素的范围：即以大写字母开始，跟着小写字母
i_start = i
i += 1
while i < N and formula[i].islower(): i += 1
name = formula[i_start: i] # 获取化学元素的名称
# 找到这个元素的个数
i_start = i
while i < N and formula[i].isdigit(): i += 1
# 元素后面没有数字，表示只有一个元素，multiplicity = 1（索引的对应范围为0）
# 元素后面有数字，表示有多个元素，multiplicity = int(formula[i_start: i])
multiplicity = int(formula[i_start: i] or 1)
# 外部的数量，加上栈顶counter中该元素原本数量
stack[-1][name] += multiplicity
# sorted() 对Counter中的key进行排序，就是按照字母表中顺序进行排序的
# 使用for取出每个化学元素，然后将化学元素与对应的频率进行合并，转为字符串
# 注意：如果一个化学元素的个数为1，那么在结果中是不展示的，所以这里需要一个if判断
return "".join(name + (str(stack[-1][name]) if stack[-1][name] > 1 else '')
for name in sorted(stack[-1]))推荐 核心方法：使用正则表达式和栈，栈的使用思路与上述相同
正则表示式为： "([A-Z][a-z]*)(\d*)|(\()|(\))(\d*)"。其中
([A-Z][a-z]*)代表匹配一个大写字符，后跟任意数量小写字符，(\d*)代表匹配任意数量的数字。(\()匹配左括号，(\))匹配右括号，(\d*)匹配任意数量的数字。
- 时间复杂度：$O(N^2)$
- 空间复杂度：$O(N)$
class Solution(object):
def countOfAtoms(self, formula):
parse = re.findall(r"([A-Z][a-z]*)(\d*)|(\()|(\))(\d*)", formula)
stack = [collections.Counter()]
for name, m1, left_open, right_open, m2 in parse:
# 每次从匹配到的结果中获取，元素名称，元素数量，左括号，右括号，括号外数量
if name:
stack[-1][name] += int(m1 or 1)
if left_open:
stack.append(collections.Counter())
if right_open:
top = stack.pop()
for k in top:
# k为元素名称，top[k]为元素对应的数量
stack[-1][k] += top[k] * int(m2 or 1)
return "".join(name + (str(stack[-1][name]) if stack[-1][name] > 1 else '')
for name in sorted(stack[-1]))151，翻转字符串里的单词，中等
核心方法：使用栈，获取每个字符
- 首先判断当前字符是否为空格，且单词是否不为空：如果满足则将单词入栈，并且单词字符串置空
- 否则，只要当前字符不为空格，将该词添加进单词字符串中，遍历完毕后，将最后的单词字符串入栈
- 依次弹出栈，空格拼接为字符串
class Solution:
def reverseWords(self, s: str) -> str:
stack = list()
tmp_str = '' # 记录一个完整的单词
for i in range(len(s)):
if s[i] == ' ' and tmp_str:
stack.append(tmp_str)
tmp_str = ''
elif s[i] != ' ':
tmp_str += s[i]
# 遍历完毕后将最后一个完整单词入栈
stack.append(tmp_str)
res = ''
while stack:
res += stack.pop() + ' '
return res.strip()496，下一个更大的元素，简单
核心方法：暴力去找
时间复杂度：$O(n^2)$
空间复杂度：$O(n)$
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
res = [0] * n
for i in range(n):
loc = nums2.index(nums1[i])
find = False
for j in range(loc+1, len(nums2)):
if nums2[j] > nums1[i]:
res[i] = nums2[j]
find = True
break
if not find :
res[i] = -1
return res核心方法：栈+哈希
首先遍历nums2，使用栈找到nums2中每个元素后面第一个比它大的元素，存入字典。外部元素大于栈顶元素的，将二者加入哈希映射，外部元素入栈。然后再遍历nums1，按序在哈希表中找到结果
时间复杂度：O(n+m)
空间复杂度：O(n)
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 首先遍历nums2，使用栈找到nums2中每个元素后面第一个比它大的元素，存入字典
# 然后再遍历nums1，按序找到结果
map_dict = dict()
stack = [nums2[0]]
for i in range(1, len(nums2)):
while stack and nums2[i] > stack[-1]:
map_dict[stack[-1]] = nums2[i]
stack.pop()
stack.append(nums2[i])
while stack:
map_dict[stack.pop()] = -1
# 开始遍历nums1
for j in range(len(nums1)):
nums1[j] = map_dict[nums1[j]]
return nums11063，有效子数组的数目，困难
核心方法：单调栈
这里需要做问题转化。要求输出的子数最左边的元素不大于其他元素，所以我们需要找到每一个元素的从其右边开始第一个小于这个元素的数，那么这两个数的索引差就是，当前元素对象（即上文的每一个元素）作为子数组的最左边值，最大能够延伸的长度，即第一个小于这个数的前一个数。比如数组，[2, 3, 4, 1]，可以看到1小于2，所以2作为子数组的开头最大能够延伸到1的前一位，就是到4，所以满足条件的子数组就是[2], [2, 3], [2, 3, 4]。
这里使用单调栈，保存我们需要确认范围的元素的下标；如果当前遍历到的元素小于栈顶元素，我们就找到了那个边界，于是将栈顶元素弹出，计算当前遍历到元素与栈顶元素的距离。
为了能将栈中所用的元素的边界全部计算完毕，可以预先在数组中加入-1，使得遍历到最后一位时，能够将栈中所有的元素全部拿出来计算他们的延伸边界。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def validSubarrays(self, nums: List[int]) -> int:
nums.append(-1)
n = len(nums)
stack = list()
res = 0
for i in range(n):
while stack and nums[stack[-1]] > nums[i]:
res += i - stack.pop()
stack.append(i)
return res上面这种方法是使用左边界的，在末尾加入的-1作为哨兵，保证栈中的元素全部能够全部弹出，计算他们作为左边界的数组个数；还可以使用一种计算右边界的方法。每次遍历一个数，当栈不为空且满足该数小于栈顶元素时，就将栈顶元素弹出，然后当前数入栈。
每次一个新数入栈都会统计当前栈的长度添加的结果中。这样做的原因是，新的数入栈时，已经能够保证这个栈是一个单调栈，如果以新入栈的元素作为数组的右边界，那么可行的数组个数就是当前栈的长度。在遍历的过程中，每次添加都统计栈的长度，最后得到的值就是所有符合要求的数组的个数。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def validSubarrays(self, nums: List[int]) -> int:
n = len(nums)
inc_stk = []
res = 0
for x in nums:
while inc_stk and inc_stk[-1] > x:
inc_stk.pop(-1)
inc_stk.append(x)
res += len(inc_stk) #以x为右端的情况
return res71，简化路径，中等
核心方法：这一种消除类的问题，可以通过栈来解决
一种比较快的方法是，直接根据按照'/'分割后得到的列表来进行遍历。遍历到的字符串，如果不属于['.', '..', '']中的任意一个，那么就将这个字符串加入栈中；如果遇到了'..'应该返回上一级，那么直接弹出栈顶元素
时间复杂度：O(n)，最坏情况下
空间复杂度：O(n)，最坏情况下
class Solution:
def simplifyPath(self, path: str) -> str:
stack = list()
for p in path.split('/'):
if p not in ['.', '..', '']:
stack.append(p)
elif p == '..' and stack:
stack.pop()
return '/' + '/'.join(stack)85，最大矩形，困难
核心方法：使用柱状图的暴力解法
- 首先计算出矩阵的每个元素的左边连续1的数量，使用二维数组
left记录，其中left[i][j]为矩阵第i行第j列元素的左边连续1的数量。 - 然后计算以
matrix[i][j]为右下角点的矩阵的面积。在计算面积时，k从当前右下角点所在的行，向上遍历。每向上一行，根据left数组更新矩阵宽度（取最小），更新矩形高度和宽度更新面积。
时间复杂度：$O(m^2n)$
空间复杂度：$O(mn)$
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])
# 求解每个点左边连续1的数量
left = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
left[i][j] = left[i][j-1] + 1
else:
left[i][j] = 0
res = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '0':
# 以 matrix[i][j] 为矩阵右下角的数
# 如果这个数为0，直接跳过，因为要求的是全1矩阵
continue
width = left[i][j]
area = width
for k in range(i-1, -1, -1):
# k 表示从下至上，每向上走一步，就根据left数组更新当前矩阵的宽度
width = min(width, left[k][j])
# 其中（i-k+1）表示矩阵高度，这个高度需要乘以宽度
area = max(area, (i - k + 1) * width)
res = max(res, area)
return res核心方法：单调栈
为了计算矩形中的最大面积，我们只需要计算每个柱状图中的最大面积，并找到全局最大值
时间复杂度：O(mn)
空间复杂度：O(mn)
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m = len(matrix)
if m == 0: return 0
n = len(matrix[0])
left = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
left[i][j] = left[i][j-1] + 1
res = 0
# 对于每一列，使用单调栈计算柱状图
for j in range(n):
down, up = [0] * m, [0] * m
stack = list()
for i in range(m):
while stack and left[stack[-1]][j] >= left[i][j]:
stack.pop()
# 这里up[i]记录的就是以matrix[i][j]基准的，向上查找到的最大矩形高度+1
# 实际上，up[i]保存的是同列中，向上第一个小于当前left的值
up[i] = stack[-1] if stack else -1
stack.append(i)
stack = list()
for i in range(m-1, -1, -1):
while stack and left[stack[-1]][j] >= left[i][j]:
stack.pop()
# 这里down[i]记录的就是以matrix[i][j]基准的，向下查找到的最大矩形高度+1
# 实际上，down[i]保存的是同列中，向下第一个小于当前left的值
down[i] = stack[-1] if stack else m
stack.append(i)
# 将向上查找和向下查找的结果统一起来，计算left每一列上的最大面积
for i in range(m):
# 注意这里，因为down和up记录的分别是第一个大于当前left，和第一个小于left的值
# 这两个值是不包含在最大范围内的，所以这个范围的大小就是两值的差，再减去1
height = down[i] - up[i] - 1
area = height * left[i][j]
res = max(area, res)
return res155，最小栈，简单
核心方法：辅助栈。
题目最核心的要求是，要在常数时间内在栈中检索到最小元素。所以可以使用一个辅助栈，每次向元素栈压入元素后，需要向辅助栈中压入栈中所有元素的最小值，这个最小值由当前新入栈元素和辅助栈中栈顶元素取最小得到。在弹出时，两个栈保持同步弹出。
时间复杂度：O(1)
空间复杂度：O(n)
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = list()
self.min_stack = [float('inf')]
def push(self, val: int) -> None:
self.stack.append(val)
self.min_stack.append(min(val, self.min_stack[-1]))
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]