面试手撕题

最小K个数（美团）--排序¶

给定一个数组nums，设计一个算法，从该数组中寻找最小的k个数。请按从小到大的顺序返回这k个数。

---

不同路径（美团）--动态规划¶

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

---

不同路径2--动态规划¶

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

---

乘积最大子数组（快手）¶

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积

---

数组中的第K个最大元素--快速选择¶

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

---

会议室2（腾讯PCG）¶

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

核心思路： 本质是求区间集合在任意时刻的最大重叠数——即同时处于"开始但尚未结束"状态的区间数量的峰值。

算法直觉： 将问题转化为"会议室资源调度"：

• 贪心思想：当新会议到来时，优先复用最早结束的会议室。若其结束时间 ≤ 新会议开始时间，则腾出该房间供复用；否则必须新开一间。

• 最小堆维护"最早结束时间"：堆顶始终是当前所有占用会议室中最早空闲的那个，O(log n) 完成插入与弹出。

In [10]:

import heapq

class Solution:
    def minMeetingRooms(self, intervals):
        """
        目标：给定一组会议 [start, end)，求最少需要多少间会议室（同一时刻 end==start 不冲突）。
        方法：最小堆（小根堆）按“结束时间”管理当前在开的会议；堆大小即并发会议数。
        """
        if not intervals:
            return 0
        # 1) 先按开始时间排序，保证按时间线从早到晚处理
        intervals.sort(key=lambda x: x[0])
        heap = []
        max_rooms = 0
        # 2) 若前面会议的结束时间小于等于下一场会议开始的时间，则可共用一间会议室
        for s, e in intervals:
            while heap and heap[0] <= s:
                heapq.heappop(heap)
            heapq.heappush(heap, e) # 放在最前面，该会议结束时间一定是最早的
            max_rooms = max(max_rooms, len(heap))

        return max_rooms
test = [[0, 30], [5, 10], [15, 20]]
print(Solution().minMeetingRooms(test))

import heapq class Solution: def minMeetingRooms(self, intervals): """ 目标：给定一组会议 [start, end)，求最少需要多少间会议室（同一时刻 end==start 不冲突）。 方法：最小堆（小根堆）按“结束时间”管理当前在开的会议；堆大小即并发会议数。 """ if not intervals: return 0 # 1) 先按开始时间排序，保证按时间线从早到晚处理 intervals.sort(key=lambda x: x[0]) heap = [] max_rooms = 0 # 2) 若前面会议的结束时间小于等于下一场会议开始的时间，则可共用一间会议室 for s, e in intervals: while heap and heap[0] <= s: heapq.heappop(heap) heapq.heappush(heap, e) # 放在最前面，该会议结束时间一定是最早的 max_rooms = max(max_rooms, len(heap)) return max_rooms test = [[0, 30], [5, 10], [15, 20]] print(Solution().minMeetingRooms(test))

2

时间O(n log n)：

• 排序 O(n log n)；
• 每个区间各执行一次 push + 至多一次 pop，单次操作 O(log n)，共 O(n log n)

空间：O(n)； 最坏情况（所有会议完全重叠）堆中存放 n 个结束时间

---

解码方法（腾讯PCG）¶

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

"1" -> 'A'

"2" -> 'B'

...

"25" -> 'Y'

"26" -> 'Z'

然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。

例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1, 1, 10, 6)

"KJF" ，将消息分组为 (11, 10, 6)

消息不能分组为 (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。 注意，可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。

核心思想 加入的元素，分为两种情况，可以单独编码吗？可以组合编码吗？互相不冲突

• （1）当加入的一个数不是0，他一定可以单独编码，那么至少 dp i= dpi_1。
• （2）当加入的一个数可以与前面的组合编码，那么至少 dpi = dpi_2

In [3]:

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if  not s or s[0] == '0':
            return 0

        dpi_2, dpi_1 = 1, 1
        
        for i in range(1, n):
            dpi = 0
            if s[i] != '0':
                dpi = dpi_1
            if s[i-1] == '1' or (s[i-1] == '2' and s[i] < '7'):
                dpi += dpi_2
            if dpi == 0:
                return 0
            dpi_2, dpi_1 = dpi_1, dpi

        return dpi_1
s = "238"
print(Solution().numDecodings(s))

class Solution: def numDecodings(self, s: str) -> int: n = len(s) if not s or s[0] == '0': return 0 dpi_2, dpi_1 = 1, 1 for i in range(1, n): dpi = 0 if s[i] != '0': dpi = dpi_1 if s[i-1] == '1' or (s[i-1] == '2' and s[i] < '7'): dpi += dpi_2 if dpi == 0: return 0 dpi_2, dpi_1 = dpi_1, dpi return dpi_1 s = "238" print(Solution().numDecodings(s))

2

二叉树节点染色的最大权值问题(字节国际电商)¶

给定一个整数数组 nums，用来按层序（level order）表示一棵二叉树。

数组规则如下：

nums[i] 表示编号为 i 的节点的权重。

若 nums[i] 为 null（或某特殊标记），表示该位置不存在节点。

对于任意下标 i：

左子节点下标为 2*i + 1

右子节点下标为 2*i + 2

若子节点下标越界或该位置为 null，则该子节点不存在。

现在你可以对若干节点进行“染色”。

染色约束：

若某节点被染色，则它的父节点不能被染色；

若某节点被染色，则它的左右子节点不能被染色；

兄弟节点之间没有限制。

目标：

在满足上述约束的前提下，选择若干节点，使得被染色节点的权重之和最大。

返回这个最大值。

核心思路

假设：

left = (L0, L1) right = (R0, R1)

那么：

L0 = 不选左孩子时的最大值； L1 = 选左孩子时的最大值； R0 = 不选右孩子时的最大值； R1 = 选右孩子时的最大值。

状态转移

情况1：选当前节点

如果你选当前节点：

那么左右孩子都不能选。

所以：

choose = 当前权重 + L0 + R0

因为：

只能拿“不选孩子”的值。

情况2：不选当前节点

如果你不选当前节点：

左右孩子可以自由选择（选或不选）

所以：

not_choose = max(L0, L1) + max(R0, R1)

In [1]:

from typing import List, Optional

class Solution:
    def maxColorValue(self, nums: List[Optional[int]]) -> int:
        n = len(nums)
        def dfs(i: int):
            """
            返回:
            (not_choose, choose)
            not_choose: 不选当前节点的最大值
            choose: 选当前节点的最大值
            """
            
            # 越界 或 节点为空
            if i >= n or nums[i] is None:
                return (0, 0)
            
            # 递归计算左右子节点
            left = dfs(2 * i + 1)
            right = dfs(2 * i + 2)
            
            # 选当前节点
            # 子节点必须不选
            choose = nums[i] + left[0] + right[0]
            
            # 不选当前节点
            # 子节点可以选或不选，取最大
            not_choose = max(left) + max(right)
            
            return (not_choose, choose)
        
        # 根节点开始
        result = dfs(0)
        
        # 最终可以选根，也可以不选根
        return max(result)
nums = [3,2,3,None,3,None,1]
print(Solution().maxColorValue(nums))

from typing import List, Optional class Solution: def maxColorValue(self, nums: List[Optional[int]]) -> int: n = len(nums) def dfs(i: int): """ 返回: (not_choose, choose) not_choose: 不选当前节点的最大值 choose: 选当前节点的最大值 """ # 越界 或 节点为空 if i >= n or nums[i] is None: return (0, 0) # 递归计算左右子节点 left = dfs(2 * i + 1) right = dfs(2 * i + 2) # 选当前节点 # 子节点必须不选 choose = nums[i] + left[0] + right[0] # 不选当前节点 # 子节点可以选或不选，取最大 not_choose = max(left) + max(right) return (not_choose, choose) # 根节点开始 result = dfs(0) # 最终可以选根，也可以不选根 return max(result) nums = [3,2,3,None,3,None,1] print(Solution().maxColorValue(nums))

7

---

代码infoNCE的函数计算公式（字节国际电商，主播自己项目所用）¶

In [30]:

import torch
import torch.nn.functional as F
def infoNCE(user_emb, item_emb, tempreture = 0.5):
    B, D = user_emb.shape
    # 归一化
    user_emb = F.normalize(user_emb, dim = -1)
    item_emb = F.normalize(item_emb, dim = -1)
    # 相似矩阵
    sim = torch.matmul(user_emb, item_emb.transpose(0, 1)) / tempreture
    # 标签
    label = torch.arange(B)
    # 多类交叉熵计算
    loss = F.cross_entropy(sim, label) # Compute the cross entropy loss between input logits and target.
    return loss
user_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
item_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
print(infoNCE(user_emb, item_emb, 1))

import torch import torch.nn.functional as F def infoNCE(user_emb, item_emb, tempreture = 0.5): B, D = user_emb.shape # 归一化 user_emb = F.normalize(user_emb, dim = -1) item_emb = F.normalize(item_emb, dim = -1) # 相似矩阵 sim = torch.matmul(user_emb, item_emb.transpose(0, 1)) / tempreture # 标签 label = torch.arange(B) # 多类交叉熵计算 loss = F.cross_entropy(sim, label) # Compute the cross entropy loss between input logits and target. return loss user_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]]) item_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]]) print(infoNCE(user_emb, item_emb, 1))

tensor(1.1176)

In [ ]:

import torch
import torch.nn.functional as F
def cross_entropy(logits, labels):
    B, _ = logits.shape
    max_logits = torch.max(logits, dim=-1, keepdim=True)[0] #返回（最大值数值，最大值的位置索引），取[0]表示取出最大值
    stable_logits = logits - max_logits     # B, D
    log_sum_exp = torch.log(torch.sum(torch.exp(stable_logits), dim=-1))    #(B,)
    pos_logits = stable_logits[torch.arange(B), labels]     # (B,)
    loss = - pos_logits + log_sum_exp
    return loss.mean()

def infoNCE(user_emb, item_emb, tempreture=0.7):
    B, D = user_emb.shape
    user_emb = F.normalize(user_emb, dim=-1)
    item_emb = F.normalize(item_emb, dim=-1)
    sim = torch.matmul(user_emb, item_emb.transpose(0,1)) / tempreture
    label = torch.arange(B)
    loss = cross_entropy(sim, label)
    return loss
user_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
item_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
print(infoNCE(user_emb, item_emb, 1))

import torch import torch.nn.functional as F def cross_entropy(logits, labels): B, _ = logits.shape max_logits = torch.max(logits, dim=-1, keepdim=True)[0] #返回（最大值数值，最大值的位置索引），取[0]表示取出最大值 stable_logits = logits - max_logits # B, D log_sum_exp = torch.log(torch.sum(torch.exp(stable_logits), dim=-1)) #(B,) pos_logits = stable_logits[torch.arange(B), labels] # (B,) loss = - pos_logits + log_sum_exp return loss.mean() def infoNCE(user_emb, item_emb, tempreture=0.7): B, D = user_emb.shape user_emb = F.normalize(user_emb, dim=-1) item_emb = F.normalize(item_emb, dim=-1) sim = torch.matmul(user_emb, item_emb.transpose(0,1)) / tempreture label = torch.arange(B) loss = cross_entropy(sim, label) return loss user_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]]) item_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]]) print(infoNCE(user_emb, item_emb, 1))

tensor(1.1176)

---

121. 买卖股票的最佳时机(字节)¶

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

核心思想

在遍历到第 i 天时， 假设第 i 天卖出，最大利润是多少？

利润 = 当前价格 − 之前某一天的最低价格

因此算法维护两个量：

cur_min_price：到当前为止出现过的最低价格（即最优买入点）。

max_profit：到当前为止能获得的最大利润。

一次遍历 + 动态维护历史最低价。

In [2]:

from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        cur_min_price = prices[0]
        max_profit = 0
        for i in range(1, n):
            cur_min_price = min(cur_min_price, prices[i])
            max_profit = max(max_profit, prices[i] - cur_min_price)
        return max_profit
prices = [7, 1, 5, 3, 6, 4]
print(Solution().maxProfit(prices))

from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) cur_min_price = prices[0] max_profit = 0 for i in range(1, n): cur_min_price = min(cur_min_price, prices[i]) max_profit = max(max_profit, prices[i] - cur_min_price) return max_profit prices = [7, 1, 5, 3, 6, 4] print(Solution().maxProfit(prices))

5

时间复杂度 O(n)

空间复杂度 O(1)

---

105. 岛屿的最大面积(腾讯WXG)¶

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

这是一个典型的二维网格 DFS / BFS 遍历问题。本质是： 遍历每个位置，遇到 1 时，向四个方向扩散，把整块连通区域面积统计出来，并取最大值。

核心思想：

1. 外层双重循环遍历整个 grid

2. 遇到 1 时启动 DFS

3. DFS 负责：

   • 累加面积
   • 把访问过的 1 置为 0（避免重复访问）
   • 向四个方向继续扩散

In [16]:

from typing import List

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        if not grid or not grid[0]:
            return 0
        
        rows = len(grid)
        cols = len(grid[0])
        max_area = 0
        
        # 定义 DFS
        def dfs(r: int, c: int) -> int:
            # 越界 或 当前是水，返回 0
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 0
            
            # 访问过的陆地置为 0，避免重复访问
            grid[r][c] = 0
            
            # 当前格子面积为 1
            area = 1
            
            # 向四个方向扩散
            area += dfs(r + 1, c)
            area += dfs(r - 1, c)
            area += dfs(r, c + 1)
            area += dfs(r, c - 1)
            
            return area
        
        # 遍历每一个位置
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    # 每次发现新岛屿，计算面积
                    current_area = dfs(i, j)
                    max_area = max(max_area, current_area)
        
        return max_area
grid = [
        [1, 1, 0, 0, 1, 1],
        [1, 1, 1, 0, 1, 1],
        [0, 1, 1, 0, 1, 0]
        ]
print(Solution().maxAreaOfIsland(grid))   

from typing import List class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: if not grid or not grid[0]: return 0 rows = len(grid) cols = len(grid[0]) max_area = 0 # 定义 DFS def dfs(r: int, c: int) -> int: # 越界 或 当前是水，返回 0 if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0: return 0 # 访问过的陆地置为 0，避免重复访问 grid[r][c] = 0 # 当前格子面积为 1 area = 1 # 向四个方向扩散 area += dfs(r + 1, c) area += dfs(r - 1, c) area += dfs(r, c + 1) area += dfs(r, c - 1) return area # 遍历每一个位置 for i in range(rows): for j in range(cols): if grid[i][j] == 1: # 每次发现新岛屿，计算面积 current_area = dfs(i, j) max_area = max(max_area, current_area) return max_area grid = [ [1, 1, 0, 0, 1, 1], [1, 1, 1, 0, 1, 1], [0, 1, 1, 0, 1, 0] ] print(Solution().maxAreaOfIsland(grid))

7

时间复杂度：

O(m × n)

每个格子最多被访问一次。

空间复杂度：

O(m × n)（最坏情况下递归栈深度为整个网格大小，例如全是 1）

如果是正常岛屿分布，递归深度通常为单个岛屿面积。

---

200. 岛屿数量¶

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

In [ ]:

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        if not grid or not grid[0]:
            return 0
        
        rows = len(grid)
        cols = len(grid[0])
        count = 0
        
        def dfs(r: int, c: int) -> None:
            # 越界 或 当前是水，直接返回
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0":
                return
            
            # 淹掉当前陆地
            grid[r][c] = "0"
            
            # 扩散四个方向
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    count += 1   # 发现一个新岛屿
                    dfs(i, j)    # 把整座岛淹掉
        
        return count

from typing import List class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid or not grid[0]: return 0 rows = len(grid) cols = len(grid[0]) count = 0 def dfs(r: int, c: int) -> None: # 越界 或 当前是水，直接返回 if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0": return # 淹掉当前陆地 grid[r][c] = "0" # 扩散四个方向 dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) for i in range(rows): for j in range(cols): if grid[i][j] == "1": count += 1 # 发现一个新岛屿 dfs(i, j) # 把整座岛淹掉 return count

时间复杂度：

O(m × n)

每个格子最多访问一次。

空间复杂度：

O(m × n)

最坏情况递归深度为整个网格。

---

最长公共子序列，输出公共子序列（字节国际电商）¶

给定两个字符串 text1 和 text2，请返回它们的最长公共子序列（Longest Common Subsequence, LCS）。

如果不存在公共子序列，返回空字符串 ""。

说明：

子序列是指在不改变字符相对顺序的情况下，通过删除某些字符（或不删除）得到的新字符串。

一个字符串的子序列可以是该字符串本身。

如果存在多个最长公共子序列，返回其中任意一个即可。

示例：

输入： text1 = "abcde" text2 = "ace"

输出： "ace"

核心思想：

需要用到输出最长公共子序列长度

1）DP 表记录的是“最优值结构”

2）回溯是在“最优值结构”上反向找路径

• 当字符相等时，一定来自左上角。
• 当字符不等时，一定来自上或左，选值更大的方向。

In [1]:

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> str:
        m, n = len(text1), len(text2)
        # dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 长度
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        print(dp)
        # 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
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        # 2. 回溯构造字符串
        print(dp)
        i, j = m, n
        res = []
        while i > 0 and j > 0:
            # 当前字符相同，说明一定在 LCS 里
            if text1[i - 1] == text2[j - 1]:
                res.append(text1[i - 1])
                i -= 1
                j -= 1
            # 否则看是从哪里转移过来的
            elif dp[i - 1][j] >= dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
        # 因为是从后往前加的，需要反转
        return ''.join(reversed(res))

text1 = "abcdefgadc"
text2 = "acebbfdc"
print(Solution().longestCommonSubsequence(text1, text2))

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> str: m, n = len(text1), len(text2) # dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 长度 dp = [[0] * (n + 1) for _ in range(m + 1)] print(dp) # 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 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 2. 回溯构造字符串 print(dp) i, j = m, n res = [] while i > 0 and j > 0: # 当前字符相同，说明一定在 LCS 里 if text1[i - 1] == text2[j - 1]: res.append(text1[i - 1]) i -= 1 j -= 1 # 否则看是从哪里转移过来的 elif dp[i - 1][j] >= dp[i][j - 1]: i -= 1 else: j -= 1 # 因为是从后往前加的，需要反转 return ''.join(reversed(res)) text1 = "abcdefgadc" text2 = "acebbfdc" print(Solution().longestCommonSubsequence(text1, text2))

[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 1, 1, 2, 2, 2, 2, 2], [0, 1, 2, 2, 2, 2, 2, 2, 3], [0, 1, 2, 2, 2, 2, 2, 3, 3], [0, 1, 2, 3, 3, 3, 3, 3, 3], [0, 1, 2, 3, 3, 3, 4, 4, 4], [0, 1, 2, 3, 3, 3, 4, 4, 4], [0, 1, 2, 3, 3, 3, 4, 4, 4], [0, 1, 2, 3, 3, 3, 4, 5, 5], [0, 1, 2, 3, 3, 3, 4, 5, 6]]
acefdc

---

最大化分堆后的最小堆大小(抖音)¶

给定一个整数数组 stones，其中 stones[i] 表示第 i 类石头的数量。每一类石头需要 单独进行拆分，不同类型之间 不能混合到同一堆中。

现在需要将所有石头拆分成 恰好 m 堆。拆分规则如下：

1. 每一类石头 stones[i] 可以被拆分成若干堆。
2. 每一堆只能包含 同一种类型的石头。
3. 所有类型拆分后的堆数之和必须 恰好等于 m。
4. 每一堆的大小为正整数。
5. 记所有堆的大小为 g₁, g₂, ..., gₘ，目标是 最大化

$$ \min(g_1, g_2, ..., g_m) $$

即希望所有堆中 最小的堆尽可能大。

输出需要包含：

• 最大可能的最小堆大小 k
• 每个 stones[i] 的具体拆分方案

输出格式

返回一个结果：

[k, groups]

其中：

• k 表示最小堆大小
• groups[i] 表示 stones[i] 的拆分结果

示例

输入

stones = [5, 8]
m = 5

解释：

• 第一类石头数量为 5
• 第二类石头数量为 8
• 需要最终得到 5 堆

一种最优拆分方案：

5 → [2,3]
8 → [2,3,3]

最终所有堆为：

[2,3,2,3,3]

最小堆大小：

min = 2

输出：

[2, [[2,3], [2,3,3]]]

In [2]:

def solve(stones: list[int], m: int):
    """
    最大化分堆后的最小堆大小
    
    Args:
        stones: 各类石头数量
        m:      目标总堆数（恰好）
    Returns:
        [k, groups]  k=最优最小堆大小, groups[i]=第i类的具体拆分列表
    """
    n = len(stones)

    # ── 边界检查 ──────────────────────────────────────────────────────────────
    # 每类石头至少需要独立 1 堆，因此 m 不能小于 n
    if m < n:
        raise ValueError(f"m={m} < n={n}，堆数不足以覆盖所有类型")

    # ── Step 1: 二分搜索最优 k ────────────────────────────────────────────────
    def feasible(k: int) -> bool:
        """
        判断"最小堆大小为 k"是否可行：
          - 每类石头必须 >= k（才能凑出至少 1 堆）
          - 所有类合计最多能拆出的堆数 >= m
        """
        total_max_heaps = 0
        for s in stones:
            if s < k:               # 连 1 堆都凑不出来
                return False
            total_max_heaps += s // k
        return total_max_heaps >= m

    lo, hi = 1, max(stones)
    while lo < hi:
        mid = (lo + hi + 1) // 2   # 上取中，防止死循环（向上逼近）
        if feasible(mid):
            lo = mid                # mid 可行 → 尝试更大
        else:
            hi = mid - 1            # mid 不可行 → 缩小上界
    k = lo                          # 最终最优最小堆大小

    # ── Step 2: 分配各类石头的堆数 c[i] ─────────────────────────────────────
    # 约束：1 ≤ c[i] ≤ floor(stones[i]/k)，且 sum(c) = m
    # 策略：先每类分 1 堆，再把剩余堆数按"可用容量"贪心分配
    c = [1] * n
    remaining = m - n               # 还需额外分配的堆数

    for i in range(n):
        if remaining == 0:
            break
        max_extra = stones[i] // k - 1     # 第 i 类还能额外承接的堆数
        add = min(remaining, max_extra)
        c[i] += add
        remaining -= add

    # ── Step 3: 按 c[i] 均匀拆分每类石头 ────────────────────────────────────
    # 将 stones[i] 拆成 c[i] 堆，尽量均匀：
    #   r = stones[i] % c[i] 堆大小为 q+1，其余 c[i]-r 堆大小为 q
    # 保证每堆 >= k（因为 c[i] <= floor(stones[i]/k) → q = floor(stones[i]/c[i]) >= k）
    groups = []
    for i in range(n):
        q, r = divmod(stones[i], c[i])
        group = [q + 1] * r + [q] * (c[i] - r)
        groups.append(group)

    return [k, groups]


## 运行结果
stones = [6, 5, 10, 9]
m = 8
print(solve(stones, m))

def solve(stones: list[int], m: int): """ 最大化分堆后的最小堆大小 Args: stones: 各类石头数量 m: 目标总堆数（恰好） Returns: [k, groups] k=最优最小堆大小, groups[i]=第i类的具体拆分列表 """ n = len(stones) # ── 边界检查 ────────────────────────────────────────────────────────────── # 每类石头至少需要独立 1 堆，因此 m 不能小于 n if m < n: raise ValueError(f"m={m} < n={n}，堆数不足以覆盖所有类型") # ── Step 1: 二分搜索最优 k ──────────────────────────────────────────────── def feasible(k: int) -> bool: """ 判断"最小堆大小为 k"是否可行： - 每类石头必须 >= k（才能凑出至少 1 堆） - 所有类合计最多能拆出的堆数 >= m """ total_max_heaps = 0 for s in stones: if s < k: # 连 1 堆都凑不出来 return False total_max_heaps += s // k return total_max_heaps >= m lo, hi = 1, max(stones) while lo < hi: mid = (lo + hi + 1) // 2 # 上取中，防止死循环（向上逼近） if feasible(mid): lo = mid # mid 可行 → 尝试更大 else: hi = mid - 1 # mid 不可行 → 缩小上界 k = lo # 最终最优最小堆大小 # ── Step 2: 分配各类石头的堆数 c[i] ───────────────────────────────────── # 约束：1 ≤ c[i] ≤ floor(stones[i]/k)，且 sum(c) = m # 策略：先每类分 1 堆，再把剩余堆数按"可用容量"贪心分配 c = [1] * n remaining = m - n # 还需额外分配的堆数 for i in range(n): if remaining == 0: break max_extra = stones[i] // k - 1 # 第 i 类还能额外承接的堆数 add = min(remaining, max_extra) c[i] += add remaining -= add # ── Step 3: 按 c[i] 均匀拆分每类石头 ──────────────────────────────────── # 将 stones[i] 拆成 c[i] 堆，尽量均匀： # r = stones[i] % c[i] 堆大小为 q+1，其余 c[i]-r 堆大小为 q # 保证每堆 >= k（因为 c[i] <= floor(stones[i]/k) → q = floor(stones[i]/c[i]) >= k） groups = [] for i in range(n): q, r = divmod(stones[i], c[i]) group = [q + 1] * r + [q] * (c[i] - r) groups.append(group) return [k, groups] ## 运行结果 stones = [6, 5, 10, 9] m = 8 print(solve(stones, m))

[3, [[3, 3], [5], [4, 3, 3], [5, 4]]]

a的b次方（阿里）¶

In [ ]:

def fast_pow(a: float, b: int) -> float:
    """
    计算 a 的 b 次方（a^b），使用快速幂算法（O(log n)）

    参数：
        a: 底数（可以是浮点数）
        b: 指数（可以是负数、0、正数）

    返回：
        a^b 的结果
    """

    # 1. 特殊情况：b == 0
    # 任何数的 0 次方为 1（包括负数和正数）
    if b == 0:
        return 1.0

    # 2. 处理负指数
    # a^(-b) = 1 / (a^b)
    if b < 0:
        return 1 / fast_pow(a, -b)

    # 3. 初始化结果
    result = 1.0

    # 4. 快速幂核心
    while b > 0:
        # 如果当前 b 是奇数
        if b % 2 == 1:
            result *= a  # 乘上当前底数
        # 底数平方
        a *= a
        # 指数右移（等价于 b //= 2）
        b //= 2
    return result

a = 4
b = 5
print(fast_pow(a, b))

def fast_pow(a: float, b: int) -> float: """ 计算 a 的 b 次方（a^b），使用快速幂算法（O(log n)） 参数： a: 底数（可以是浮点数） b: 指数（可以是负数、0、正数） 返回： a^b 的结果 """ # 1. 特殊情况：b == 0 # 任何数的 0 次方为 1（包括负数和正数） if b == 0: return 1.0 # 2. 处理负指数 # a^(-b) = 1 / (a^b) if b < 0: return 1 / fast_pow(a, -b) # 3. 初始化结果 result = 1.0 # 4. 快速幂核心 while b > 0: # 如果当前 b 是奇数 if b % 2 == 1: result *= a # 乘上当前底数 # 底数平方 a *= a # 指数右移（等价于 b //= 2） b //= 2 return result a = 4 b = 5 print(fast_pow(a, b))

1024.0

可以把这段算法理解为：一边读取指数 (b) 的二进制，一边决定“这一位要不要用”，同时把底数不断升级为更高次幂。

用一个具体例子说明：计算 (2^{13})。

先把 13 写成二进制： $ 13 = 1101_2 = 1 + 4 + 8 $

算法从最低位开始处理（从右往左）：

• 初始：a = 2，b = 13，result = 1

第1轮：b=13（奇数）

• “奇数”意味着：当前二进制最低位是 1 → 这一位要用
• 所以：result *= a → result = 2
• 然后 a 平方：a = 4（表示下一位对应的 (2^2)）
• b 整除 2：b = 6（相当于右移一位，从 1101 → 110）

第2轮：b=6（偶数）

• 偶数 → 当前位是 0 → 这一位不用
• result 不变
• a 平方：a = 16（现在表示 (2^4)）
• b // 2：b = 3（110 → 11）

第3轮：b=3（奇数）

• 奇数 → 当前位是 1 → 要用
• result *= a → result = 2 × 16 = 32
• a 平方：a = 256（表示 (2^8)）
• b // 2：b = 1（11 → 1）

第4轮：b=1（奇数）

• 奇数 → 要用
• result *= a → result = 32 × 256 = 8192
• a 平方（无所谓了）
• b // 2 → 0（结束）

核心本质（关键解释你卡住的点）

• “b 是奇数 → 乘” 本质是：当前二进制位是 1，需要把这一位对应的幂乘进去

• “b //= 2” 本质是：把指数右移一位，去看下一位（二进制）

一句话总结

这段代码其实是在做：

从低位到高位扫描 b 的二进制：遇到 1 就乘当前幂，同时每一步把底数平方以对应更高位。

如果用最直观的话讲：

“b 是奇数”不是数学技巧，而是“这一位是 1”； “b 除以 2”也不是随便除，而是“去看下一位”。

经典鸡蛋掉落问题¶

给定 k 个鸡蛋 和一栋共有 n 层楼 的建筑，存在一个未知的临界楼层 (f)（满足 (0 \le f \le n)），使得：

• 从 高于第 (f) 层 的楼层扔下鸡蛋，鸡蛋一定会碎；
• 从 第 (f) 层或以下 的楼层扔下鸡蛋，鸡蛋一定不会碎；
• 每次只能选择一个鸡蛋，从任意一层楼扔下；
• 一旦鸡蛋碎掉，该鸡蛋不能再使用；
• 未碎的鸡蛋可以重复使用。

目标是：

设计一种策略，在 最坏情况下测试次数最少，确定这个临界楼层 (f) 的具体数值。

需要求解的问题是：

在给定 k 个鸡蛋 和 n 层楼 的条件下，最少需要多少次测试（最坏情况下），才能保证一定能够确定临界楼层 (f)。

形式化表达为：

输入：

• 整数 (k)：鸡蛋数量
• 整数 (n)：楼层数量

输出：

• 一个整数，表示最坏情况下确定临界楼层所需的最少测试次数

例如：

示例 1： 输入： k = 1, n = 2 输出： 2 解释： 只有一个鸡蛋时只能线性扫描：从第 1 层开始逐层测试。

示例 2： 输入： k = 2, n = 6 输出： 3

示例 3： 输入： k = 3, n = 14 输出： 4

整体分析¶

在正式进入两种思路之前，我想先帮你理清这道题为什么"难"，以及难在哪里。

这道题的本质困难在于：我们面对的是一个"最坏情况下的最优策略"问题。注意这两个关键词的叠加——"最坏情况"意味着对手会专门选择让你测试次数最多的临界层；"最优策略"意味着你需要在这种假设下，找到一个让总次数尽可能少的方法。因此它既不是纯粹的贪心，也不是简单的二分，而是一个需要通过动态规划来穷举所有策略并取最优的过程。

很多同学做不出来，往往卡在一个思维定势上：直觉上会想"我能不能二分？"答案是不完全能——鸡蛋数量的限制打破了二分的前提条件。如果你只有一个鸡蛋，你根本不敢从中间层扔，因为一旦碎了就再也无法向上探索。这个"资源约束"是这道题核心复杂性的来源。

两种思路的区别在于如何定义状态。思路一是"正向思维"：给定资源（蛋数和楼层），求代价（测试次数）。思路二是"逆向思维"：给定资源（蛋数）和代价（测试次数的预算），求能力（能确定多少层）。后者更为精妙，也是这道题最优解的来源。

---

思路一：dp[i][j] — 给定 i 个蛋、j 层楼，最少需要多少次？¶

核心状态定义

令 dp[i][j] 表示：在有 i 个鸡蛋、楼层数为 j 的情况下，最坏情况下确定临界层所需的最少测试次数。

这是最自然的定义方式，你已经比较熟悉它，所以我在这里重点讲状态转移方程的推导逻辑，确保你真正吃透。

状态转移的推导

假设我们有 i 个鸡蛋、j 层楼，我们决定在第 x 层（1 ≤ x ≤ j）扔下一个鸡蛋，此时有两种结果：

第一，鸡蛋碎了。说明临界层在第 x 层以下（1 到 x-1 层），我们损失了一个鸡蛋，此后子问题规模变为 dp[i-1][x-1]。

第二，鸡蛋没碎。说明临界层在第 x 层及以上（x 到 j 层），鸡蛋完好，此后子问题规模变为 dp[i][j-x]（因为 x 层以上还有 j-x 层未确认）。

由于对手会选对我们最不利的结果，所以这次扔蛋的"实际代价"是两种结果中的最大值（最坏情况）。我们在所有可能的楼层 x 中选择让这个最大值最小的那个，因此：

dp[i][j] = 1 + min over x in [1, j] of { max(dp[i-1][x-1], dp[i][j-x]) }

这里的 1 代表这一次扔蛋本身消耗了一次机会。

一个关键的优化观察

朴素地枚举所有 x 的时间复杂度是 O(k·n²)，对于 n=10000 这样的数据会超时。注意到：随着 x 增大，dp[i-1][x-1] 单调递增（楼层越多越难确定），而 dp[i][j-x] 单调递减（剩余楼层越少越容易）。最优的 x 就在这两条曲线的交叉点附近，可以用二分搜索来定位，将时间复杂度降至 O(k·n·log n)。

Python 代码实现

def superEggDrop_dp1(k: int, n: int) -> int:
    # dp[i][j] 表示 i 个蛋、j 层楼时的最少测试次数
    # 用字典做记忆化，避免初始化整个二维数组
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(eggs, floors):
        # 边界条件
        if eggs == 1:
            return floors        # 只有一个蛋，只能逐层线性扫描
        if floors == 0:
            return 0             # 没有楼层，不需要测试
        if floors == 1:
            return 1             # 只有一层，测一次即可
        
        # 二分搜索最优的扔蛋楼层 x
        lo, hi = 1, floors
        while lo + 1 < hi:
            mid = (lo + hi) // 2
            # 蛋碎（往下找）vs 没碎（往上找）的代价
            break_case = dp(eggs - 1, mid - 1)  # 蛋碎，检查 mid 以下
            safe_case  = dp(eggs, floors - mid)  # 没碎，检查 mid 以上
            
            if break_case < safe_case:
                lo = mid     # 往上移动以减小 safe_case
            elif break_case > safe_case:
                hi = mid     # 往下移动以减小 break_case
            else:
                lo = hi = mid
        
        # 在 lo 和 hi 两个候选点取最优
        ans = 1 + min(
            max(dp(eggs - 1, lo - 1), dp(eggs, floors - lo)),
            max(dp(eggs - 1, hi - 1), dp(eggs, floors - hi))
        )
        return ans
    
    return dp(k, n)

思路一的好处是直观，状态含义清晰；缺点是即使加了二分优化，对于极大的 n（如 10^9）仍然无法应对。这就引出了思路二的必要性。

---

思路二：dp[k][m] — 给定 k 个蛋、m 次机会，最多能确定多少层？¶

核心状态定义（思维反转）

这是这道题最精彩的洞见。我们不再问"需要多少次"，而是反过来问"给我 m 次机会，我能确定多少层"。

令 dp[k][m] 表示：有 k 个鸡蛋、恰好 m 次测试机会，在最优策略下，最多能确定（即：保证一定能找到临界层）的楼层总数。

最终答案就是：找到最小的 m，使得 dp[k][m] ≥ n。

状态转移的推导（这是精华）

有 k 个蛋、m 次机会，我们从某一层 x 扔下一个蛋，仍然有两种结果：

第一，蛋碎了。剩余资源变为 k-1 个蛋、m-1 次机会。根据 dp 定义，这能够确定 dp[k-1][m-1] 层楼（即 x 层以下这么多层）。

第二，蛋没碎。剩余资源变为 k 个蛋、m-1 次机会，能够确定 dp[k][m-1] 层楼（即 x 层以上这么多层）。

加上第 x 层本身（这一层已经通过这次测试被确认了），我们总共能覆盖的楼层数为：

dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1

这个公式之所以优美，是因为它与 x 的选择完全无关——无论我们选在哪一层扔，能覆盖的总楼层数都是这个值。这意味着最优策略天然地将两部分分配均衡，不需要额外优化。

边界条件

dp[0][m] = 0（没有蛋，什么都确认不了），dp[k][0] = 0（没有机会，什么都确认不了），dp[1][m] = m（一个蛋只能线性扫描，m 次最多确认 m 层）。

Python 代码实现

def superEggDrop_dp2(k: int, n: int) -> int:
    # dp[k][m] = 有 k 个蛋、m 次机会，最多能确定多少层
    # m 的上界不超过 n（最坏情况也就用 n 次）
    
    # 用一维滚动数组节省空间：dp[j] 表示当前蛋数下，j 次机会能确定的楼层数
    # 从 m=1 开始迭代，直到 dp[k] >= n 为止
    
    dp = [0] * (n + 1)  # dp[m]，初始蛋数为 1 时，m 次=m 层（稍后处理）
    
    # 外层循环：测试次数 m 从 1 开始递增
    # 内层循环：蛋的数量从 k 递减到 1（注意更新顺序很关键）
    
    # 重新用二维 dp 让逻辑更清晰
    # dp2[i][j] 表示 i 个蛋 j 次机会能确定的楼层数
    # 为节省空间，用两行滚动
    
    prev = list(range(n + 1))   # 1 个蛋时：dp[1][m] = m
    
    for eggs in range(2, k + 1):
        curr = [0] * (n + 1)
        for moves in range(1, n + 1):
            # 核心递推式
            curr[moves] = prev[moves - 1] + curr[moves - 1] + 1
            # 一旦能确定 >= n 层，后续的 moves 不需要再算了
            if curr[moves] >= n:
                # 此时 moves 就是答案（对于这个 eggs 数量）
                # 但我们继续填满数组以备后用
                pass
        prev = curr
    
    # 找最小的 m 使得 prev[m] >= n
    for m in range(1, n + 1):
        if prev[m] >= n:
            return m
    return n  # 保底（理论上不会到这里）


# 更简洁的版本，直接找答案
def superEggDrop_dp2_clean(k: int, n: int) -> int:
    # dp[j] 代表当前蛋数 + j 次机会能覆盖的最大楼层数
    # 初始化为 1 个蛋的情况
    dp = list(range(n + 1))  # dp[m] = m（1个蛋时，m次能查m层）
    
    for _ in range(k - 1):   # 蛋从 2 增加到 k，共需迭代 k-1 次
        new_dp = [0] * (n + 1)
        for m in range(1, n + 1):
            new_dp[m] = dp[m - 1] + new_dp[m - 1] + 1
            # 提前退出：一旦已经可以覆盖 n 层就不必继续
        dp = new_dp
    
    # 找最小的 m 使得 dp[m] >= n
    for m in range(1, n + 1):
        if dp[m] >= n:
            return m
    return n

思路二的最大优势在于：m 的最大值不超过 O(log n)（因为即使是二分搜索，log₂(10^9) ≈ 30），所以整体时间复杂度是 O(k log n)，可以轻松应对 n 极大的情况。

---

两种思路的对比总结¶

思路一的状态 dp[i][j] 直接对应问题描述，容易理解，适合作为入门解法；其瓶颈在于对极大 n 无能为力。思路二的状态 dp[k][m] 来自一个"维度互换"的洞见——将"需要多少次"变成"给定次数能覆盖多少"，不仅推导出了优雅的递推式，还将时间复杂度从 O(kn) 压缩到了 O(k log n)，是面试中体现深度思维的解法。

---

如何培养动态规划思维¶

这是你问的最有价值的问题。动态规划能力的核心不是"记住模板"，而是培养三种感知能力。

第一，识别"最优子结构 + 重叠子问题"的嗅觉。 每当你看到"最少/最多/最大/最小"，同时问题的规模可以通过决策分解为更小的同类问题时，就应该条件反射地想到 DP。鸡蛋问题中，"最少次数"和"可以递归拆分为更小的蛋数+楼层子问题"这两个信号同时出现。

第二，学会从多角度定义状态。 这是最难培养的能力，也是区分普通解法与优雅解法的关键。对同一个问题，不同的状态定义会导致截然不同的时间复杂度（如本题的 O(kn²) vs O(k log n)）。训练方法是：做完一道题后，强迫自己换一个视角重新定义状态，看看能否推导出新的递推式，再比较两种方法的优劣。

第三，区间、序列、树形 DP 的模式识别。 大多数 DP 题目属于几个固定的范式：线性 DP（如爬楼梯、打家劫舍）、区间 DP（如矩阵链乘、括号问题）、背包类（如 0/1 背包、完全背包）、树形 DP（如二叉树上的最优路径）。鸡蛋问题属于比较特殊的"资源约束下的策略优化"类型，与这些主流范式都有所不同，需要单独积累。

推荐训练路径，按梯度排列如下。LeetCode 上有一条官方的 DP 学习路径，建议严格按顺序完成：从第 70 题（爬楼梯）、第 198 题（打家劫舍）建立基础直觉，然后挑战第 322 题（零钱兑换）掌握一维背包，再到第 1143 题（最长公共子序列）理解二维 DP，最终攻克第 312 题（戳气球）这样的区间 DP 难题，以及本题（第 887 题）这样的高阶题目。

在思维方法论上，强烈推荐阅读《算法导论》第 15 章（动态规划），它对"最优子结构的证明"有非常严格的讲解，读完后你对 DP 的理解会从"会用"上升到"知其所以然"。此外，neetcode.io 提供了分类清晰的视频讲解，每道题都有从暴力到最优的完整推导过程，非常适合你这个阶段使用。

最后一个窍门：每道 DP 题做完后，写下"如果把状态定义换一种方式，会发生什么"这样的反思笔记。 鸡蛋问题的思路二就是这样被发现的——有人在思路一的基础上问了一句"如果我把代价和能力互换，会得到什么"，然后推导出了更优雅的解法。这种主动换视角的习惯，是区分能解题和真正理解 DP 的核心差异。

In [7]:

def superEggDrop(k: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    
    for j in range(1, n + 1):
        dp[1][j] = j
        
    for i in range(2, k + 1):
        for j in range(1, n + 1):
            dp[i][j] = float('inf')
            
            for x in range(1, j + 1):
                worst = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
                dp[i][j] = min(dp[i][j], worst)
                
    return dp[k][n]
k, n = 2, 10
print(superEggDrop(k, n))

def superEggDrop(k: int, n: int) -> int: dp = [[0] * (n + 1) for _ in range(k + 1)] for j in range(1, n + 1): dp[1][j] = j for i in range(2, k + 1): for j in range(1, n + 1): dp[i][j] = float('inf') for x in range(1, j + 1): worst = 1 + max(dp[i - 1][x - 1], dp[i][j - x]) dp[i][j] = min(dp[i][j], worst) return dp[k][n] k, n = 2, 10 print(superEggDrop(k, n))

4

先建立一个关键直觉：你的"预算"和"步长"必须匹配

我先不讲代码，先讲一个思维实验。假设你只有 2 个鸡蛋、10 层楼，然后我问你：你敢不敢从第 5 层开始扔？

你应该感到不安。为什么？因为一旦鸡蛋在第 5 层碎了，你只剩 1 个蛋，而你还不知道临界层在 1、2、3、4 层中的哪一层，你只能从第 1 层开始一层一层往上试。这 4 层就要花掉你 4 次，加上之前在第 5 层的那 1 次，总共 5 次。

然后你从第 5 层换到第 8 层继续，如果在第 8 层碎了，你又要线性扫描第 6、7 层，又要花 2 次，加上第 8 层那 1 次，总共已经用了 1（第5层）+ 1（第8层）+ 2 = 4次……等等，其实在不同楼层决策，最坏情况的次数是不同的。这里直觉已经开始混乱了——这正是你感到"想不出来"的根本原因：层与层之间的代价是不均衡的。

两个鸡蛋问题的核心约束：你的步长必须"递减"

现在我来给你建立正确的直觉。

用 2 个蛋解决问题，本质上是一个"一次性探测 + 线性兜底"的两阶段策略。第一个蛋负责"跳跃式定位大区间"，一旦它碎了，第二个蛋就只能在那个小区间里逐层线性扫描。

这意味着：如果你第一个蛋用了 m 次跳跃，那每次跳跃后，万一碎了，你的线性扫描代价必须控制在剩余次数之内。

具体来说，假设你给自己设定总次数预算为 t 次，那么：

第 1 次扔，你选择第 t 层。为什么是 t 层？因为如果它碎了，你还剩 t-1 次和 1 个蛋，你最多能线性扫描 t-1 层（即第 1 层到第 t-1 层），恰好够用。

如果第 1 次没碎，你上移，第 2 次扔第 t + (t-1) 层。为什么步长变成了 t-1？因为此时你已经花掉了 1 次，预算只剩 t-1，万一碎了，你只能再扫描 t-2 层，所以这个区间的大小只能是 t-1。

以此类推，每上跳一次，步长就减少 1。这就是"递减步长"策略，也是 2 个蛋问题的最优解结构。

那么 t 次总共能覆盖多少层？就是 t + (t-1) + (t-2) + ... + 1 = t(t+1)/2。

现在直接回答：2个蛋10层楼最坏需要几次？

你需要找最小的 t，使得 t(t+1)/2 ≥ 10：

当 t = 3 时：3×4/2 = 6，覆盖不了 10 层，不够。

当 t = 4 时：4×5/2 = 10，恰好覆盖 10 层，答案就是 4 次。

具体策略是这样执行的：第一次在第 4 层扔（步长 4），第二次在第 7 层扔（步长 3），第三次在第 9 层扔（步长 2），第四次在第 10 层扔（步长 1）。我来逐一验证最坏情况：

场景一：第 4 层碎了 → 线性扫描 1、2、3 层 → 最多再用 3 次 → 总共 1 + 3 = 4 次。

场景二：第 4 层没碎，第 7 层碎了 → 线性扫描 5、6 层 → 再用 2 次 → 总共 1 + 1 + 2 = 4 次。

场景三：第 4、7 层没碎，第 9 层碎了 → 线性扫描第 8 层 → 再用 1 次 → 总共 1 + 1 + 1 + 1 = 4 次。

场景四：第 4、7、9 层都没碎，第 10 层扔下去 → 无论碎没碎都能确定答案 → 总共 4 次。

每种最坏情况都恰好是 4 次。这正是"递减步长"策略的精妙之处：它让每种最坏情况的代价完全均等，没有任何一种情况比其他情况多花一次，这就是最优性的体现。

回到你的代码：x 的枚举到底在做什么？

现在你再看这段代码，感觉就不一样了：

for x in range(1, j + 1):
    worst = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
    dp[i][j] = min(dp[i][j], worst)

这里枚举 x 的本质，就是在模拟"我在哪一层扔第一个蛋"这个决策。对于每一个候选的 x，max(...) 计算了在那一层扔下去之后的最坏情况代价，而 min(...) 则是在所有候选楼层中挑出让最坏情况最轻的那个决策——也就是我们上面分析的"步长递减"策略在数学上的等价表达。

你之前卡壳的点是"没想到要枚举 x"，其实这恰恰是 DP 里最重要的思维动作：用穷举来代替"直觉上找不到规律"的决策。当你无法直接想清楚"应该在哪层扔最优"时，就枚举所有可能，让 min-max 结构替你找出最优决策。这个模式在很多 DP 题里反复出现，比如矩阵链乘、戳气球，本质都是"枚举决策点，取最优"。

建立这种直觉的方法很简单：下次遇到最优化 + 递归子结构的题，先问自己"这道题的核心决策是什么"，再问"这个决策有哪些候选值"，然后大胆地全部枚举，用 min/max 取优。不要一开始就想"哪个选择最优"——你可能根本想不出来，但机器可以帮你枚举出来。先把"穷举 + 剪枝"的框架搭对，优化（比如二分加速）是后面的事。

---

题目：长度不超过 k 的连续子数组最大和¶

给定一个整数数组 nums（长度为 n，元素可正可负）以及一个正整数 k，请找出所有长度不超过 k 的非空连续子数组中，和最大的那个，返回该最大和。

输入：整数数组 nums，正整数 k（1 ≤ k ≤ n）。

输出：一个整数，表示所有满足条件的连续子数组中的最大和。

示例：

输入：nums = [2, -1, 5, -3, 4]，k = 3
输出：6
解释：子数组 [2, -1, 5] 长度为 3，不超过 k=3，其和为 6，是所有合法子数组中最大的。

约束条件：

1 ≤ k ≤ n ≤ 10^5
-10^4 ≤ nums[i] ≤ 10^4

In [1]:

def maxSumWithLengthK_brute(nums, k):
    n = len(nums)
    # 前缀和
    P = [0] * (n + 1)
    for i in range(n):
        P[i + 1] = P[i] + nums[i]
    
    ans = float('-inf')
    for j in range(1, n + 1):          # 右端点
        for i in range(max(0, j - k), j):  # 左端点，窗口长度不超过k
            ans = max(ans, P[j] - P[i])
    
    return ans
nums = [1, 2, 4, 10, 5, 0, 100]
k = 3
print(maxSumWithLengthK_brute(nums,  k))

def maxSumWithLengthK_brute(nums, k): n = len(nums) # 前缀和 P = [0] * (n + 1) for i in range(n): P[i + 1] = P[i] + nums[i] ans = float('-inf') for j in range(1, n + 1): # 右端点 for i in range(max(0, j - k), j): # 左端点，窗口长度不超过k ans = max(ans, P[j] - P[i]) return ans nums = [1, 2, 4, 10, 5, 0, 100] k = 3 print(maxSumWithLengthK_brute(nums, k))

105

暴力枚举时，固定右端点 j，然后遍历所有合法左端点 i，逐个计算 P[j] - P[i] 并取最大值。当右端点移动到 j+1 时，又重新遍历一遍合法左端点。这里的冗余是：对左端点集合的"找最小值"操作，在每个右端点处都从零开始重做了一遍，但左端点集合的变化其实非常有规律——每次只是右边新增一个候选、左边可能淘汰一个过期的。

对于右端点 j，我们需要的不是"把所有合法左端点都比一遍"，而是"直接知道合法左端点中前缀和最小的那一个"。如果我们能始终维护一个数据结构，使得这个最小值随时可以 O(1) 读取，那么每个右端点只需要做一次减法，整体就降为 O(n)。 单调队列正是这个数据结构。它的队头，始终存放的是当前合法窗口内前缀和最小的左端点。右端点每向右移动一步，队列只做两件轻量的事情：从左边淘汰过期的下标，从右边加入新候选并维护单调性。读答案时直接用 running - dq[0]，不需要任何遍历。

用一句话总结:

暴力的代价在于：每个右端点都重新"扫描"一遍左端点集合来找最小值。单调队列的贡献在于：把这个"找最小值"的过程增量化——左端点集合每次只变化一点点，队列以 O(1) 摊还代价跟踪这个变化，使得每个右端点可以直接 O(1) 读取最优左端点，而不是重新扫描。

In [ ]:

from collections import deque

def maxSumWithLengthK(nums, k):
    n = len(nums)

    # 前缀和
    P = [0] * (n + 1)
    for i in range(n):
        P[i + 1] = P[i] + nums[i]

    ans = float('-inf')
    dq = deque()  # 存下标，队头到队尾 P[i] 单调递增

    for j in range(1, n + 1):
        # 1. 先把合法的左端点 i = j - k 加入队列
        i = j - 1  # 当前右端点 j 对应的新候选左端点
        # 队尾弹出：维护单调递增（P[i] 更小，队尾更大的没有意义）更小的前缀和永远更优
        while dq and P[dq[-1]] >= P[i]:
            dq.pop()
        dq.append(i)

        # 2. 队头弹出：左端点过期（窗口长度超过 k）
        #    合法左端点范围：i >= j - k
        while dq and dq[0] < j - k:
            dq.popleft()

        # 3. 队头就是当前窗口内 P[i] 最小的左端点
        ans = max(ans, P[j] - P[dq[0]])

    return ans

from collections import deque def maxSumWithLengthK(nums, k): n = len(nums) # 前缀和 P = [0] * (n + 1) for i in range(n): P[i + 1] = P[i] + nums[i] ans = float('-inf') dq = deque() # 存下标，队头到队尾 P[i] 单调递增 for j in range(1, n + 1): # 1. 先把合法的左端点 i = j - k 加入队列 i = j - 1 # 当前右端点 j 对应的新候选左端点 # 队尾弹出：维护单调递增（P[i] 更小，队尾更大的没有意义）更小的前缀和永远更优 while dq and P[dq[-1]] >= P[i]: dq.pop() dq.append(i) # 2. 队头弹出：左端点过期（窗口长度超过 k） # 合法左端点范围：i >= j - k while dq and dq[0] < j - k: dq.popleft() # 3. 队头就是当前窗口内 P[i] 最小的左端点 ans = max(ans, P[j] - P[dq[0]]) return ans