栈、队列与单调栈

import sys

s = sys.stdin.readline().strip()
match = {")": "(", "]": "[", "}": "{"}     # 右括号 → 应配对的左括号
stack = []
best = 0
valid = True
for ch in s:
    if ch in "([{":
        stack.append(ch)
        best = max(best, len(stack))       # 入栈之后栈的大小就是当前嵌套深度
    else:
        if not stack or stack[-1] != match.get(ch):   # 栈空、或栈顶类型不配对
            valid = False
            break
        stack.pop()
if stack:                                  # 扫完还有没配对的左括号
    valid = False
print(best if valid else 0)

自测建议：题面五组示例，再加空串（输出 0）与 (()（输出 0）。

import sys

data = sys.stdin.read().split()
n = int(data[0])
heights = [int(x) for x in data[1:1 + n]]

ans = [0] * n                              # 找不到更高的人 → 0
stack = []                                 # 存下标；自底向上身高不升
for i, h in enumerate(heights):
    while stack and h > heights[stack[-1]]:   # 严格更高才结算
        j = stack.pop()
        ans[j] = i                         # 题面示例证明输出的是下标（从 0 起）
    stack.append(i)
print(" ".join(str(x) for x in ans))

自测建议：题面两组示例，以及 n=0（输出空行）；想进一步验证，可写一个 O(n²) 向右扫描的暴力程序，用随机输入对拍。

import sys

s = sys.stdin.readline().strip()

def read_num(i):                           # 从位置 i 读一段连续数字；没有数字按 1
    if i >= len(s) or not s[i].isdigit():
        return 1, i
    num = 0
    while i < len(s) and s[i].isdigit():
        num = num * 10 + int(s[i])
        i += 1
    return num, i

stack = [""]                               # 每一层花括号一张「草稿」；栈底是最外层
i = 0
while i < len(s):
    ch = s[i]
    if ch == "{":
        stack.append("")                   # 进入新的一层
        i += 1
    elif ch == "}":
        num, i = read_num(i + 1)           # } 后面的数字属于整个花括号
        seg = stack.pop()
        stack[-1] += seg * num             # 展开后拼回上一层
    else:
        num, i = read_num(i + 1)           # 普通字符后面的数字
        stack[-1] += ch * num
print(stack[0])

自测建议：题面两组示例、两位数重复次数 {AB}12，以及第 10 节练习 5 的三层嵌套。

import sys

lines = sys.stdin.read().split("\n")
n = int(lines[0])
adjust = 0
disordered = False                         # 当前队列是否已经乱序（需要在下次取数前调整）
removed = 0                                # 已经取走了几个数 → 队列里最小的数应是 removed + 1
for line in lines[1:1 + 2 * n]:
    parts = line.split()
    if parts[0] == "remove":
        if disordered:
            adjust += 1                    # 取数前调整一次，整队变有序
            disordered = False
        removed += 1
    elif parts[0] == "head":
        x = int(parts[2])
        if x != removed + 1:               # 队列非空（里面还有比 x 小的数）时从头部加入 → 乱序
            disordered = True
    # tail add：加入的数总是最大的，接在尾部不打乱顺序
print(adjust)

自测建议：题面示例（输出 1）、第 06 节第二组（输出 2）；想进一步验证，可与「真实双端队列 + 队头不对就整体排序」的模拟对拍。

def max_depth(s):
    match = {")": "(", "]": "[", "}": "{"}
    stack = []
    best = 0
    for ch in s:
        if ch in "([{":
            stack.append(ch)
            best = max(best, len(stack))      # 入栈之后再取最大值
        else:
            if not stack or stack[-1] != match.get(ch):
                return 0                      # 栈空 / 类型不配对 → 无效
            stack.pop()
    return best if not stack else 0           # 收尾有剩 → 无效

assert max_depth("(()(()))") == 3
assert max_depth(")(") == 0      # 右括号先出现，无效
assert max_depth("(()") == 0     # 收尾栈非空，无效
assert max_depth("") == 0        # 空串按题目要求处理
assert max_depth("([]{()})") == 3   # 题面示例
assert max_depth("([)]") == 0       # 数量相等但顺序错

六条断言覆盖：常规、右括号先出现、收尾有剩、空串、题面示例、数量相等顺序错。