- 单调栈就是栈中存放的数据都是有序的；
- 而由于栈有先进后出的限制，使得每次入栈都需要判断与栈顶元素的关系，如果会破坏单调的性质，则需要将栈顶元素出栈，直到满足条件为止；
模拟图示
- python 中使用队列，推荐标准库实现
collections.deque；其入队和出队的操作分别为.append(x)和.popleft()如果用
list来模拟队列，其出队操作.pop(0)的时间复杂度为O(N)；而deque的.popleft()只要O(1)；
LeetCode 0020 有效的括号 (简单, 2022-03)剑指Offer 0600 从尾到头打印链表 (简单, 2021-11)剑指Offer 0900 用两个栈实现队列 (简单, 2021-11)剑指Offer 0900 用两个栈实现队列 (简单, 2021-11)剑指Offer 3000 包含min函数的栈 (简单, 2021-11)剑指Offer 3100 栈的压入、弹出序列 (中等, 2021-11)剑指Offer 3201 层序遍历二叉树 (简单, 2021-11)剑指Offer 3202 层序遍历二叉树 (简单, 2021-11)剑指Offer 3203 层序遍历二叉树（之字形遍历） (简单, 2021-11)剑指Offer 5902 队列的最大值 (中等, 2022-01)牛客 0014 按之字形顺序打印二叉树 (中等, 2022-01)牛客 0049 最长的括号子串 (较难, 2022-03)牛客 0052 有效括号序列 (简单, 2022-03)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。- 利用栈，遇到左括号就压栈，遇到右括号就出栈；
- 无效的情况：栈顶与当前遇到的右括号不匹配，或栈为空；
- 当遍历完所有字符，且栈为空时，即有效；
Python
class Solution:
def isValid(self, s: str) -> bool:
""""""
N = len(s)
# 奇数情况一定无效
if N % 1: return False
# 小技巧，遇到左括号，压入对应的右扩招，这样遇到右括号对比时，直接比较即可
book = {'(': ')', '[': ']', '{': '}'}
stk = []
for c in s:
if c in book:
stk.append(book[c])
else:
# 如果栈为空，或者栈顶不匹配，无效
if not stk or stk[-1] != c:
return False
stk.pop()
return len(stk) == 0
从尾到头打印链表（用数组返回）详细描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 法1）利用栈，顺序入栈，然后依次出栈即可
- 法2）利用深度优先遍历思想（二叉树的先序遍历）
Python：栈
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
stack = []
while head:
stack.append(head.val)
head = head.next
# ret = []
# for _ in range(len(stack)): # 相当于逆序遍历
# ret.append(stack.pop())
# return ret
return stack[::-1] # 与以上代码等价Python：DFS、递归
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if head is None:
return []
ret = self.reversePrint(head.next)
ret.append(head.val)
return ret
用两个栈实现一个队列。
队列包含两个函数 appendTail 和 deleteHead(若队列中没有元素，deleteHead 操作返回 -1 )详细描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 栈：先进后出；队列：先进先出；换言之，队列就是倒序输出的栈；
- 利用双栈可实现倒序输出：维护两个栈 A 和 B，将 A 中元素依次弹出并压入栈 B，再依次弹出 B 中元素，即实现了对栈 A 元素的倒序输出，即实现了队列的性质；
Python
class CQueue:
def __init__(self):
self.I = [] # 入栈
self.O = [] # 出栈
def appendTail(self, value: int) -> None:
self.I.append(value) # 新元素全部加到 I
def deleteHead(self) -> int:
if self.O: # 如果 O 不为空
return self.O.pop() # 弹出栈顶元素
if not self.I: # 如果 I 为空，说明队列为空
return -1
while self.I: # 如果 I 不为空，但 O 为空，此时将 I 中元素依次加入 O
self.O.append(self.I.pop())
return self.O.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
用两个栈实现一个队列。
队列包含两个函数 appendTail 和 deleteHead(若队列中没有元素，deleteHead 操作返回 -1 )详细描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 栈：先进后出；队列：先进先出；换言之，队列就是倒序输出的栈；
- 利用双栈可实现倒序输出：维护两个栈 A 和 B，将 A 中元素依次弹出并压入栈 B，再依次弹出 B 中元素，即实现了对栈 A 元素的倒序输出，即实现了队列的性质；
Python
class CQueue:
def __init__(self):
self.I = [] # 入栈
self.O = [] # 出栈
def appendTail(self, value: int) -> None:
self.I.append(value) # 新元素全部加到 I
def deleteHead(self) -> int:
if self.O: # 如果 O 不为空
return self.O.pop() # 弹出栈顶元素
if not self.I: # 如果 I 为空，说明队列为空
return -1
while self.I: # 如果 I 不为空，但 O 为空，此时将 I 中元素依次加入 O
self.O.append(self.I.pop())
return self.O.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
实现栈的 pop 和 push 方法，同时实现一个 min 方法，返回栈中的最小值，min、push 及 pop 的时间复杂度都是 O(1)。详细描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示：
- 各函数的调用总次数不超过 20000 次
- pop、top 和 min 操作总是在 非空栈 上调用。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 使用两个 list: Buf 和 Min；其中 Buf 正常模拟栈，Min 也是一个栈，但是它只会将小于等于栈顶的元素入栈；
- 当 Buf 的出栈元素等于 Min 的栈顶元素时，Min 也出栈；
- Python 中 list 自带的
append和pop方法默认行为就是栈的push和pop，top方法返回Buf[-1]即可；
Python
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.Buf = []
self.Min = []
def push(self, x: int) -> None:
self.Buf.append(x)
if not self.Min or x <= self.Min[-1]: # 注意这里是小于等于
self.Min.append(x)
def pop(self) -> None:
x = self.Buf.pop()
if x == self.Min[-1]:
self.Min.pop()
def top(self) -> int:
return self.Buf[-1]
def min(self) -> int:
return self.Min[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。详细描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 设置一个模拟栈 s，将 pushed 中的元素顺序入栈；
- 期间，如果 popped 中的元素与 s 栈顶元素相同，则弹出栈顶元素，直到不再相同或 s 为空；
- 当结束循环时，如果 s 不为空，则返回 False，反之 True；
Python
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
s = [] # 模拟栈
# pop(0) 的操作很浪费时间，其实是不需要修改 pushed 和 popped 的，详见优化后的代码
while pushed:
s.append(pushed.pop(0))
while s and s[-1] == popped[0]:
s.pop()
popped.pop(0)
return True if not popped else FalsePython：优化后
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
s = [] # 模拟栈
idx = 0 # popped 索引
for x in pushed:
s.append(x)
while s and s[-1] == popped[idx]:
s.pop()
idx += 1
return True if not s else False
层序遍历二叉树详细描述
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
节点总数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 利用辅助队列 q；
- 将树的根结点入队；
- 如果 q 不为空，则将头结点出队记为 node；如果 node 的左节点不为空，则将左节点入队；如果 node 的右节点不为空，则将右节点入队；
- 重复 2、3，直到 q 为空
Python
list也可以模拟队列，为什么还要用collections.deque？list.pop(0)的时间复杂度为O(N)；而deque.popleft()只要O(1)；
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
from collections import deque
if not root: return []
buf = deque([root]) # 队列
ret = []
while buf:
cur = buf.popleft() # 弹出队列头
ret.append(cur.val)
if cur.left:
buf.append(cur.left)
if cur.right:
buf.append(cur.right)
return retC++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> ret;
queue<TreeNode*> q; // 辅助队列
if (root)
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
ret.push_back(node->val);
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
return ret;
}
};
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。详细描述
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
提示：
节点总数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 相比 “层序遍历二叉树-1”，本题需要同时记录当前层的节点数量（写法1）；
- 实际上每一层的节点数量包含在了保存的队列信息中，详见（写法2）；
Python：写法1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if not root: return []
buf = deque([root])
cnt = 1 # 记录当前层的节点数量
ret = []
while buf:
tmp = [] # 记录层结果
for _ in range(cnt): # 循环当前层节点数量的次数，期间改变 cnt 不会影响遍历次数
cur = buf.popleft()
tmp.append(cur.val)
cnt -= 1
if cur.left:
buf.append(cur.left)
cnt += 1
if cur.right:
buf.append(cur.right)
cnt += 1
ret.append(tmp)
return retPython：写法2
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if not root: return []
buf = deque([root])
ret = []
while buf:
tmp = []
for _ in range(len(buf)):
cur = buf.popleft()
tmp.append(cur.val)
if cur.left:
buf.append(cur.left)
if cur.right:
buf.append(cur.right)
ret.append(tmp)
return ret
按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。详细描述
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
提示：
节点总数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 在“层序遍历二叉树-2”的基础上，加入奇偶层的处理即可；
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if not root: return []
buf = deque([root])
lv = 1 # 记录当前层数
cnt = 1 # 记录当前层的节点数
ret = []
while buf:
tmp = []
for _ in range(cnt):
cur = buf.popleft()
tmp.append(cur.val)
cnt -= 1
if cur.left:
buf.append(cur.left)
cnt += 1
if cur.right:
buf.append(cur.right)
cnt += 1
# 上面的代码跟 层序遍历二叉树-2 完全相同，
# 在将 tmp 加入 ret 时，对偶数层的 tmp 做一下倒序
if lv & 1: # 奇数层
ret.append(tmp)
else:
ret.append(tmp[::-1])
lv += 1
return ret
设计一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 返回 -1详细描述
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 使用单调队列维护一个最大值序列，每次入队或出队时维护，详见代码；
Python
class MaxQueue:
def __init__(self):
from collections import deque
self.q = deque() # 正常保存队列元素
self.d = deque() # 单调队列
def max_value(self) -> int:
if not self.d: return -1
return self.d[0]
def push_back(self, value: int) -> None:
self.q.append(value)
# 维护单调队列
while self.d and self.d[-1] < value: # 这里使用小于而不是小于等于，是因为后面出队是通过值判断，所以不能使用严格单调
self.d.pop()
self.d.append(value)
def pop_front(self) -> int:
if not self.q: return -1
v = self.q.popleft()
if v == self.d[0]: # 如果出队元素等于当前最大元素，则同时对 d 执行出队
self.d.popleft()
return v
# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()
层序遍历二叉树，按之字形打印每层。- 队列 + 奇偶讨论，思路比较简单，因为需要把层分离，所以需要借助的辅助变量比较多，详见代码；
Python
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return int整型二维数组
#
class Solution:
def Print(self , pRoot: TreeNode) -> List[List[int]]:
# write code here
if not pRoot: return []
from collections import deque
ret = []
q = deque()
q.append(pRoot)
cnt = 1
nxt = 0 # 下一层需要遍历的节点数
lv = 0 # 已经遍历的层数
tmp = [] # 当前层缓存的节点数
while cnt:
cnt -= 1
node = q.popleft()
tmp.append(node.val)
if node.left:
q.append(node.left)
nxt += 1
if node.right:
q.append(node.right)
nxt += 1
if cnt == 0:
if lv % 2:
ret.append(tmp[::-1])
else:
ret.append(tmp)
tmp = []
lv += 1
cnt = nxt
nxt = 0
return ret
给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。Python
class Solution:
def longestValidParentheses(self , s: str) -> int:
stk = [-1]
ret = 0
for i, c in enumerate(s):
if c == '(':
stk.append(i)
else:
stk.pop()
if not stk:
stk.append(i)
ret = max(ret, i - stk[-1])
return ret
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。- 遇到左括号入栈，否则出栈；
- 出栈时，看括号是否匹配；
- 无效条件，中途遇到了不匹配的括号；最后栈不为空；
- 小技巧：
- 遇到左括号，可以压栈对应的右括号，这样出栈匹配时做等值比较就可以了；
- 奇数串直接返回 False；
Python
class Solution:
def isValid(self, s: str) -> bool:
if len(s) & 1: return False
stk = []
book = {'(': ')', '[': ']', '{': '}'}
for c in s:
if c in book:
stk.append(book[c])
else:
if not stk or stk[-1] != c:
return False
stk.pop()
return False if stk else True