无旋转限制的n log n时间复杂度箱子堆叠问题求解

问题规则 #

• 箱子表示为元组 (x, y, height)
• 禁止旋转箱子
• 堆叠要求：将箱子b1放在b2上方时，必须满足 b1.x <= b2.x 且 b1.y <= b2.y
• 目标：求堆叠箱子的高度总和最大值

现有尝试的痛点 #

按单轴（如x轴）排序后，针对y轴套用标准LIS（最长递增子序列）算法无法实现O(n log n)复杂度——标准LIS以序列长度为优化目标，而此处需要以高度总和为目标，两者逻辑不匹配，无法直接复用。

解法思路 #

1. 先排序箱子 #

按x轴升序排序，若x值相同则按y轴升序排序。这样处理后，后续遍历的箱子x值不会大于前面的箱子，只需专注处理y轴与高度总和的关系。

2. 改造LIS算法（动态规划+二分优化） #

我们需要维护两个数组：

• dp：存储对应高度总和下，序列末尾箱子的最小y值（保证后续能容纳更多箱子）
• sum_heights：存储对应的高度总和

遍历每个箱子时执行以下操作：

1. 用二分查找在dp中找到第一个大于当前箱子y值的位置idx
2. 计算当前箱子能贡献的高度总和：若idx=0，则总和为当前箱子的height；否则为sum_heights[idx-1] + 当前height
3. 如果idx等于dp的长度，说明可以扩展序列，将当前y值加入dp，对应的总和加入sum_heights；否则，若当前总和大于sum_heights[idx]，则更新dp[idx]为当前y值，sum_heights[idx]为当前总和

最终sum_heights中的最大值就是答案。

示例验证 #

输入：[(1,100,3),(2,1,100)]

1. 排序后得到 [(1,100,3), (2,1,100)]
2. 处理第一个箱子：dp为空，添加100，sum_heights添加3
3. 处理第二个箱子：二分找到第一个大于1的位置是0，计算总和为100，大于sum_heights[0]的3，于是更新dp[0]为1，sum_heights[0]为100
4. sum_heights最大值为100，与示例输出一致

复杂度分析 #

• 排序阶段：O(n log n)
• 遍历+二分查找：O(n log n)
• 整体复杂度：O(n log n)

代码实现（Python） #

def max_stack_height(boxes):
    # 按x升序排序，x相同则按y升序排序
    boxes.sort(key=lambda b: (b[0], b[1]))
    dp = []  # 存储对应高度总和下的最小y值
    sum_heights = []  # 存储对应的高度总和
    
    for x, y, h in boxes:
        # 二分查找第一个大于y的索引
        left, right = 0, len(dp)
        while left < right:
            mid = (left + right) // 2
            if dp[mid] > y:
                right = mid
            else:
                left = mid + 1
        idx = left
        
        # 计算当前可能的高度总和
        current_sum = h if idx == 0 else sum_heights[idx-1] + h
        
        # 更新dp和sum_heights数组
        if idx == len(dp):
            dp.append(y)
            sum_heights.append(current_sum)
        else:
            if current_sum > sum_heights[idx]:
                dp[idx] = y
                sum_heights[idx] = current_sum
    
    return max(sum_heights) if sum_heights else 0

# 测试示例
boxes = [(1,100,3),(2,1,100)]
print(max_stack_height(boxes))  # 输出：100

内容的提问来源于stack exchange，提问作者Pavlo Shevchyk