矩形操作算法优化：提升历史矩形适配查询的运行效率

核心优化思路 #

暴力法每次检查所有历史矩形，时间复杂度为O(n)/次查询，当操作量较大时会明显超时。优化的关键在于维护历史矩形的「极限标准化尺寸」：

• 对每个新增的矩形，先做标准化处理：将宽高调整为 min(a,b) 和 max(a,b)（保证宽≤高）
• 维护两个全局变量：max_normalized_width 和 max_normalized_height，分别记录所有标准化后矩形的最大宽、最大高

处理查询操作[1,a,b]时：

1. 同样将查询的矩形标准化为 q_w = min(a,b)，q_h = max(a,b)
2. 只需判断 max_normalized_width ≤ q_w 且 max_normalized_height ≤ q_h：
   • 满足则所有历史矩形都能放入目标矩形（最大的能放下，更小的自然也能放下）
   • 不满足则返回false

思路合理性说明 #

一个矩形能放入目标矩形（可旋转）的充要条件是：矩形标准化后的宽≤目标标准化后的宽，且矩形标准化后的高≤目标标准化后的高。只要历史中最大的标准化宽高都不超过目标的标准化宽高，所有历史矩形必然都能适配。

代码示例（Python） #

def solve_rectangle_operations(operations):
    max_w = 0
    max_h = 0
    result = []
    for op in operations:
        if op[0] == 0:
            # 新增矩形，标准化并更新极限尺寸
            w = min(op[1], op[2])
            h = max(op[1], op[2])
            max_w = max(max_w, w)
            max_h = max(max_h, h)
        else:
            # 处理查询，标准化目标矩形后判断
            q_w = min(op[1], op[2])
            q_h = max(op[1], op[2])
            result.append(max_w <= q_w and max_h <= q_h)
    return result

复杂度分析 #

• 单操作时间复杂度：O(1)，无论新增还是查询都只需常数级计算
• 空间复杂度：O(1)（除存储结果的数组外，无需保存所有历史矩形）

内容的提问来源于stack exchange，提问作者David Ip