📖 动态规划完全指南（40+经典问题 · 面试高频全覆盖）¶

def climb_stairs_recursive(n):
    """
    递归解法
    时间：O(2^n) - 指数级 ❌
    空间：O(n) - 递归栈
    """
    if n <= 2:
        return n

    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# 递归树（n=4）：
#                4
#              /   \
#             3     2
#            / \   / \
#           2   2 1   1
#          / \
#         1   1
#
# 可以看到重复计算：2被计算了多次！
# 这就是需要优化的原因

def climb_stairs_memo(n, memo=None):
    """
    记忆化递归（自顶向下的DP）
    时间：O(n)
    空间：O(n)
    """
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]  # 直接返回存储的结果

    if n <= 2:
        return n

    memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
    return memo[n]

def climb_stairs_dp(n):
    """
    动态规划（自底向上）
    时间：O(n)
    空间：O(n) → 可优化到O(1)
    """
    if n <= 2:
        return n

    # dp[i] = 爬到第i阶的方法数
    dp = [0] * (n + 1)
    dp[1] = 1  # 爬到第1阶：1种方法 (1)
    dp[2] = 2  # 爬到第2阶：2种方法 (1+1, 2)

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 状态转移方程

    return dp[n]

def climb_stairs_optimized(n):
    """
    空间优化版（只需保存前两个状态）
    时间：O(n)
    空间：O(1) ✅
    """
    if n <= 2:
        return n

    prev, curr = 1, 2  # dp[1], dp[2]

    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr

    return curr

# 状态转移详解：
# n=1: 1种方法                    → dp[1] = 1
# n=2: 2种方法   (1+1, 2)         → dp[2] = 2
# n=3: 3种方法   (1+1+1, 1+2, 2+1) → dp[3] = dp[2] + dp[1] = 3
# n=4: 5种方法                     → dp[4] = dp[3] + dp[2] = 5
# n=5: 8种方法                     → dp[5] = dp[4] + dp[3] = 8
#
# 发现规律：斐波那契数列！
# dp[i] = dp[i-1] + dp[i-2]

def min_cost_climbing_stairs(cost):
    """
    时间：O(n)
    空间：O(1)
    """
    n = len(cost)

    # dp[i] = 到达第i阶的最低花费
    # 状态转移：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

    prev2, prev1 = 0, 0  # dp[0], dp[1]（可以从地面直接到第0阶或第1阶）

    for i in range(2, n + 1):
        # 当前状态可以从前1阶或前2阶到达
        # 选项1：从第i-1阶爬1步，花费 = prev1 + cost[i-1]
        # 选项2：从第i-2阶爬2步，花费 = prev2 + cost[i-2]
        current = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
        prev2, prev1 = prev1, current

    return prev1

# 图解（cost = [10, 15, 20]）：
#
# 楼梯结构：
# 顶部（目标）
#   ↑
# 2阶（cost=20）
#   ↑
# 1阶（cost=15）
#   ↑
# 0阶（cost=10）
#   ↑
# 地面
#
# 起点选择：
# 选项1: 从地面到0阶，cost=0（可以直接站在第0阶）
# 选项2: 从地面到1阶，cost=0（可以直接站在第1阶）
#
# dp[0] = 0（在地面）
# dp[1] = 0（可以从地面直接到1阶）
# dp[2] = min(dp[1] + cost[1], dp[0] + cost[0])
#       = min(0 + 15, 0 + 10)
#       = 10
# dp[3] = min(dp[2] + cost[2], dp[1] + cost[1])
#       = min(10 + 20, 0 + 15)
#       = 15 ✓
#
# 最优路径：地面 → 第1阶(0) → 顶部(15)

def rob(nums):
    """
    时间：O(n)
    空间：O(1)
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    # dp[i] = 偷窃前i间房屋能获得的最大金额
    # 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    prev2, prev1 = 0, nums[0]  # dp[-1], dp[0]

    for i in range(1, len(nums)):
        # 选项1: 不偷第i间，取prev1（前i-1间的最大金额）
        # 选项2: 偷第i间，取prev2 + nums[i]（前i-2间的金额 + 当前的钱）
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1

# 状态转移详解：
# nums = [2, 7, 9, 3, 1]
#
# 初始化：
# prev2 = 0（没有房屋）
# prev1 = 2（第0间）
#
# i=1 (nums[1]=7):
#   选项1: 不偷第1间，金额 = prev1 = 2
#   选项2: 偷第1间，金额 = prev2 + 7 = 0 + 7 = 7
#   dp[1] = max(2, 7) = 7
#
# i=2 (nums[2]=9):
#   选项1: 不偷第2间，金额 = prev1 = 7
#   选项2: 偷第2间，金额 = prev2 + 9 = 2 + 9 = 11
#   dp[2] = max(7, 11) = 11
#
# i=3 (nums[3]=3):
#   选项1: 不偷第3间，金额 = prev1 = 11
#   选项2: 偷第3间，金额 = prev2 + 3 = 7 + 3 = 10
#   dp[3] = max(11, 10) = 11
#
# i=4 (nums[4]=1):
#   选项1: 不偷第4间，金额 = prev1 = 11
#   选项2: 偷第4间，金额 = prev2 + 1 = 11 + 1 = 12
#   dp[4] = max(11, 12) = 12 ✓
#
# 最优方案：偷第0、2、4间 → 2 + 9 + 1 = 12

def rob_ii(nums):
    """
    房屋排成一圈（首尾相连）
    思路：分解为两个问题
    1. 偷窃[0, n-2]（不偷最后一间）
    2. 偷窃[1, n-1]（不偷第一间）
    取两者最大值
    """
    if len(nums) == 1:
        return nums[0]

    return max(rob_range(nums, 0, len(nums) - 1),
               rob_range(nums, 1, len(nums)))

def rob_range(nums, start, end):
    """偷窃nums[start..end-1]"""
    prev2, prev1 = 0, 0

    for i in range(start, end):
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1

def generate_pascal_triangle(numRows):
    """
    时间：O(n²)
    空间：O(n²)
    """
    if numRows <= 0:
        return []

    triangle = [[1]]

    for i in range(1, numRows):
        prev_row = triangle[-1]
        current_row = [1]  # 每行第一个元素总是1

        # 中间元素 = 上一行的左上 + 右上
        for j in range(1, i):
            current_row.append(prev_row[j - 1] + prev_row[j])

        current_row.append(1)  # 每行最后一个元素总是1
        triangle.append(current_row)

    return triangle

# 状态转移详解：
# triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
#
#     1
#    1 1
#   1 2 1    → 2 = 1 + 1
#  1 3 3 1   → 3 = 1 + 2, 3 = 2 + 1
# 1 4 6 4 1  → 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1

def longest_common_subsequence(text1: str, text2: str) -> int:
    """
    dp[i][j] = text1[:i] 和 text2[:j] 的最长公共子序列长度
    时间：O(m*n)  空间：O(m*n)
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1   # 字符匹配，左上角+1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 取上方或左方最大
    return dp[m][n]

# 图解：text1="abcde", text2="ace"
#     ""  a  c  e
# ""   0  0  0  0
# a    0  1  1  1
# b    0  1  1  1
# c    0  1  2  2
# d    0  1  2  2
# e    0  1  2  3  ← LCS长度=3, LCS="ace"

def min_distance(word1: str, word2: str) -> int:
    """
    dp[i][j] = word1[:i] → word2[:j] 的最少操作次数
    操作：插入/删除/替换
    时间：O(m*n)  空间：O(m*n)
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化：空串到word2[:j]需j次插入
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(m + 1):
        dp[i][0] = i

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # 字符相同，无需操作
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除 word1[i-1]
                    dp[i][j - 1],      # 插入 word2[j-1]
                    dp[i - 1][j - 1]   # 替换
                )
    return dp[m][n]

# 图解：word1="horse", word2="ros"
#      ""  r  o  s
# ""    0  1  2  3
# h     1  1  2  3
# o     2  2  1  2
# r     3  2  2  2
# s     4  3  3  2
# e     5  4  4  3  ← 最少3次操作
# 路径：horse → rorse(替换h→r) → rose(删除r) → ros(删除e)

def unique_paths(m: int, n: int) -> int:
    """
    dp[i][j] = 到达(i,j)的不同路径数
    转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能向右或向下）
    """
    dp = [[1] * n for _ in range(m)]  # 第一行/列只有1种走法
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

# 空间优化：O(n)
def unique_paths_opt(m: int, n: int) -> int:
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[n - 1]

def min_path_sum(grid):
    """dp[i][j] = 到达(i,j)的最小路径和"""
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    return dp[m - 1][n - 1]

def knapsack_01(weights, values, capacity):
    """
    0-1背包：每个物品只能选一次
    dp[i][w] = 前i个物品，容量为w时的最大价值
    时间：O(n*W)  空间：O(n*W) → 可优化到O(W)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]  # 不选第i个物品
            if w >= weights[i - 1]:
                dp[i][w] = max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1])  # 选第i个
    return dp[n][capacity]

# ★ 空间优化版（一维滚动数组，逆序遍历）
def knapsack_01_opt(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # ★ 逆序！
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

# 关键：0-1背包必须逆序遍历容量，否则同一物品会被重复选取

def knapsack_complete(weights, values, capacity):
    """
    完全背包：每个物品可以选无限次
    与0-1背包唯一区别：容量正序遍历
    """
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(weights[i], capacity + 1):  # ★ 正序！
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

def coin_change(coins, amount):
    """最少硬币数凑出amount（完全背包求最小值）"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for j in range(coin, amount + 1):  # 正序 = 完全背包
            dp[j] = min(dp[j], dp[j - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

def change(amount, coins):
    """凑出amount的组合数（完全背包求组合数）"""
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:                    # ★ 外层遍历物品
        for j in range(coin, amount + 1): # 内层遍历容量
            dp[j] += dp[j - coin]
    return dp[amount]

# 注意：如果内外层反过来（先遍历容量再遍历物品），求的是排列数！
# LeetCode 377 组合总和Ⅳ 就是排列数版本

def find_target_sum_ways(nums, target):
    """
    将数组分为正数集P和负数集N：
    sum(P) - sum(N) = target
    sum(P) + sum(N) = total
    → sum(P) = (target + total) / 2
    转化为：从nums中选若干数使其和为(target+total)/2的方案数
    """
    total = sum(nums)
    if (target + total) % 2 != 0 or abs(target) > total:
        return 0
    bag = (target + total) // 2
    dp = [0] * (bag + 1)
    dp[0] = 1
    for num in nums:
        for j in range(bag, num - 1, -1):  # 逆序 = 0-1背包
            dp[j] += dp[j - num]
    return dp[bag]

def can_partition(nums):
    """能否将数组分成两个和相等的子集 → 0-1背包目标=sum/2"""
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

def max_coins(nums):
    """
    dp[i][j] = 戳破(i,j)开区间内所有气球能获得的最大硬币数
    关键：逆向思维 — 考虑最后一个被戳破的气球k
    """
    nums = [1] + nums + [1]  # 两端加虚拟气球
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):       # 区间长度
        for i in range(0, n - length):  # 左端点
            j = i + length              # 右端点
            for k in range(i + 1, j):   # k是最后一个被戳的
                dp[i][j] = max(dp[i][j],
                    dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
    return dp[0][n - 1]

def merge_stones(stones):
    """相邻石子合并，求最小代价（经典区间DP）"""
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[i]

    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k + 1][j] + prefix[j + 1] - prefix[i])
    return dp[0][n - 1]

def tsp(dist):
    """
    dp[mask][i] = 已访问集合为mask，当前在城市i时的最短路径
    mask用二进制表示已访问状态：0101表示访问了城市0和城市2
    时间：O(n² · 2^n)  空间：O(n · 2^n)
    """
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 从城市0出发

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask & (1 << u)):
                continue
            for v in range(n):
                if mask & (1 << v):  # v已经访问过
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v],
                                      dp[mask][u] + dist[u][v])

    full_mask = (1 << n) - 1
    return min(dp[full_mask][i] + dist[i][0] for i in range(n))

mask & (1 << i)      # 检查第i位是否为1（城市i是否已访问）
mask | (1 << i)      # 将第i位设为1（标记访问城市i）
mask ^ (1 << i)      # 翻转第i位
mask & (mask - 1)    # 去掉最低位的1
bin(mask).count('1') # 已访问城市数量

def max_path_sum(root):
    """
    经典树形DP：自底向上传递信息
    每个节点返回：经过该节点的最大单边路径和
    全局维护：经过该节点的最大路径和（可包含两边）
    """
    result = [float('-inf')]

    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)   # 负数不选
        right = max(dfs(node.right), 0)

        # 经过当前节点的最大路径（可能包含左右子树）
        result[0] = max(result[0], left + node.val + right)

        # 返回：向上传递的最大单边路径
        return node.val + max(left, right)

    dfs(root)
    return result[0]

def rob_tree(root):
    """
    dp返回: (偷当前节点的最大值, 不偷当前节点的最大值)
    """
    def dfs(node):
        if not node:
            return (0, 0)
        left = dfs(node.left)
        right = dfs(node.right)

        rob = node.val + left[1] + right[1]       # 偷当前 → 不能偷子节点
        not_rob = max(left) + max(right)           # 不偷当前 → 子节点可偷可不偷
        return (rob, not_rob)

    return max(dfs(root))

# 所有股票问题都可以用统一框架：
# dp[i][k][0] = 第i天，最多k次交易，不持有股票的最大利润
# dp[i][k][1] = 第i天，最多k次交易，持有股票的最大利润
#
# 转移方程：
# dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])  # 不动 or 卖出
# dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])  # 不动 or 买入

def max_profit_1(prices):
    """只能买卖一次"""
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

def max_profit_2(prices):
    """可以买卖无限次"""
    return sum(max(prices[i] - prices[i - 1], 0)
               for i in range(1, len(prices)))

def max_profit_3(prices):
    """最多买卖两次"""
    buy1 = buy2 = float('-inf')
    sell1 = sell2 = 0
    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)
    return sell2

def max_profit_4(k, prices):
    """最多买卖k次 — 通用解法"""
    n = len(prices)
    if k >= n // 2:  # k足够大，退化为无限次
        return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, n))

    dp = [[0, float('-inf')] for _ in range(k + 1)]  # [sell, buy]
    for price in prices:
        for j in range(1, k + 1):
            dp[j][0] = max(dp[j][0], dp[j][1] + price)
            dp[j][1] = max(dp[j][1], dp[j - 1][0] - price)
    return dp[k][0]

def max_profit_cooldown(prices):
    """卖出后需冷冻一天"""
    if len(prices) < 2:
        return 0
    hold, sold, rest = float('-inf'), 0, 0
    for price in prices:
        prev_sold = sold
        sold = hold + price            # 持有 → 卖出
        hold = max(hold, rest - price) # 休息 → 买入
        rest = max(rest, prev_sold)    # 卖出后 → 休息（冷冻）
    return max(sold, rest)

def max_profit_fee(prices, fee):
    """每次交易扣手续费"""
    hold, cash = float('-inf'), 0
    for price in prices:
        hold = max(hold, cash - price)
        cash = max(cash, hold + price - fee)
    return cash

def is_match(s: str, p: str) -> bool:
    """
    dp[i][j] = s[:i] 与 p[:j] 是否匹配
    '.' 匹配任意单字符
    '*' 匹配零个或多个前面的元素
    """
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # 初始化：空串s可以匹配 a*b*c* 这种模式
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # 匹配零次：dp[i][j-2]
                dp[i][j] = dp[i][j - 2]
                # 匹配一次或多次（前一字符匹配s[i-1]）
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

def longest_palindrome_subseq(s: str) -> int:
    """dp[i][j] = s[i..j]中最长回文子序列长度"""
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

def count_substrings(s: str) -> int:
    """dp[i][j] = s[i..j]是否为回文"""
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                count += 1
    return count

# 更优解法：中心扩展 O(n²) 时间 O(1) 空间
def count_substrings_expand(s: str) -> int:
    count = 0
    for center in range(2 * len(s) - 1):
        left = center // 2
        right = left + center % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

def word_break(s: str, wordDict) -> bool:
    """dp[i] = s[:i] 是否可以被拆分"""
    word_set = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]

# 二维DP → 一维（当前行只依赖上一行时）
# 原始：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
# 优化：dp[j] = dp[j-1] + dp[j]  （注意遍历方向！）

# 0-1背包：逆序遍历（每个物品只选一次）
for w in range(capacity, weight - 1, -1):
    dp[w] = max(dp[w], dp[w - weight] + value)

# 完全背包：正序遍历（每个物品可选多次）
for w in range(weight, capacity + 1):
    dp[w] = max(dp[w], dp[w - weight] + value)

# 记忆化搜索（自顶向下） — 适合状态空间稀疏时
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(i, j):
    if base_case: return ...
    return transition(solve(i-1, j), solve(i, j-1))

# 递推（自底向上） — 适合状态空间稠密时，通常更快
dp = [[0] * n for _ in range(m)]
for i in range(m):
    for j in range(n):
        dp[i][j] = transition(dp[i-1][j], dp[i][j-1])

# 当转移需要区间和时，预处理前缀和避免重复计算
# 石子合并：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i..j))
# 用prefix[j+1] - prefix[i] 替代循环求和

from collections import deque

def max_sliding_window_dp(nums, k):
    """滑动窗口最大值 — 单调队列 O(n)"""
    dq = deque()
    result = []
    for i, num in enumerate(nums):  # enumerate同时获取索引和值
        while dq and nums[dq[-1]] <= num:  # 负索引：从末尾倒数访问元素
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result